/* Author: 
   Date: 09-04-2008
   Filename: 
   Description: Merge Sort Algorithm
   History: 
*/


package com.chapter2;

public class MergeSortV2 {

	/**
	 * @param args
	 */
	static void Merge(int A[],int p, int q, int r)
	{
		int n1 = q-p+1;
		int n2 = r-q;
		int L[] = new int[n1+2];
		int R[] = new int[n2+2];
		for(int i = 1; i <= n1; i++)
		{
			L[i] = A[p+i-1];
		}
		for(int j = 1; j <= n2; j++)
		{
			R[j] = A[q+j];
		}
		L[n1+1] = Integer.MAX_VALUE;
		R[n2+1] = Integer.MAX_VALUE;
		int i = 1;
		int j = 1;
		for(int k = p; k <= r; k++)
		{
			if(L[i] < R[j])
			{
				A[k] = L[i];
				i++;
			}
			else
			{
				A[k] = R[j];
				j++;
			}
		}
	}
	static void MergeSort(int A[],int p, int r)
	{
		if(p<r)
		{
			int q = (p+r)/2;
			MergeSort(A, p, q);
			MergeSort(A, q+1, r);
			Merge(A, p, q, r);
			
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int arr[] = {6,23,33,1,5,77};
		MergeSort(arr,1,5);
		for(int i = 0; i < 6; i++)
		{
			System.out.println(arr[i]);
		}
	}

}