import java.util.Random;
import java.util.Scanner;

public class MergeSort2 {
	static final int MAX = 10005;
	static int[] a = new int[MAX];

	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		System.out.print("Enter Max array size: ");
		int n = input.nextInt();
		Random random = new Random();
		System.out.println("Enter the array elements: ");
		for (int i = 0; i < n; i++)
		//	a[i] = input.nextInt(); // for keyboard entry
		 a[i] = random.nextInt(1000); // generate random numbers – 
// uniform distribution
		long startTime = System.nanoTime();
		MergeSortAlgorithm(0, n - 1);
		long stopTime = System.nanoTime();
		long elapsedTime = stopTime - startTime;
		System.out.println("Time Complexity (ms) for n = " + 
n + " is : " + (double) elapsedTime / 1000000); 
		System.out.println("Sorted Array (Merge Sort):");
		for (int i = 0; i < n; i++)
			System.out.print(a[i] + " ");
		input.close();
	}

	public static void MergeSortAlgorithm(int low, int high) {
		int mid;
		if (low < high) {
			mid = (low + high) / 2;
			MergeSortAlgorithm(low, mid);
			MergeSortAlgorithm(mid + 1, high);
			Merge(low, mid, high);
		}
	}

	public static void Merge(int low, int mid, int high) {
		int[] b = new int[MAX];
		int i, h, j, k;
		h = i = low;
		j = mid + 1;
		while ((h <= mid) && (j <= high))
			if (a[h] < a[j])
				b[i++] = a[h++];
			else
				b[i++] = a[j++];

		if (h > mid)
			for (k = j; k <= high; k++)
				b[i++] = a[k];
		else
			for (k = h; k <= mid; k++)
				b[i++] = a[k];

		for (k = low; k <= high; k++)
			a[k] = b[k];
	}
}