import java.util.*;

class MergeSort
{
	public static void swap(int[] data, int x, int y)
	{
		int temp = data[x];
		data[x] = data[y];
		data[y] = temp;
	}
	
	public static void merge(int[] data, int left, int mid, int right)
	{
		int[] A;
		A = new int[mid-left+2];

		int[] B;
		B = new int[right-mid+1];

		int i;

		// Copy the first half into A
		for(i = left; i <= mid; i++)
			A[i-left] = data[i];

		// Place infinity in the last slot of A
		A[A.length-1] = Integer.MAX_VALUE;

		// Copy the second half into B
		for(i = mid+1; i <= right; i++)
			B[i-(mid+1)] = data[i];

		// Place infinity in the last slot of B
		B[B.length-1] = Integer.MAX_VALUE;
		
		i = 0;		// index for A
		int j = 0;	// index for B
		int l;

		// A and B are merged back into data
		for(l = left; l <= right; l++)
		{
			if(A[i] <= B[j])
			{
				data[l] = A[i];
				i++;
			}
			else
			{
				data[l] = B[j];
				j++;
			}
		}		


	}

	public static void recursiveMergeSort(int[] data, int left, int right)
	{
		if (left < right)
		{
			int mid = (left + right)/2;
			recursiveMergeSort(data, left, mid);
			recursiveMergeSort(data, mid+1, right);
			merge(data, left, mid, right);
		}
	}

	public static void mergeSort(int[] data, int n)
	{
		recursiveMergeSort(data, 0, n-1);
	}
	
	public static void main(String[] args)
	{

			// Generate a random integer array of size n
			int[] data;
			int n = 10;
			data = new int[n];
			
			// Random is a java class defined in java.util	
			// To learn more about this class see 
			// http://java.sun.com/j2se/1.4.2/docs/api/java/util/Random.html
			Random rand;
			rand = new Random();

			for(int i = 0; i < n; i++)
				data[i] = rand.nextInt(20);

			for(int i = 0; i < n; i++)
				System.out.print(data[i]+" ");

			System.out.println();

			mergeSort(data, n);
			for(int i = 0; i < n; i++)
				System.out.print(data[i]+" ");

			System.out.println();
	}
}