public class MergeSort {
	
	public static int count = 0;
	
	public static void main(String args[]) {
		int size = 16;
		int a[] = new int[size];

		for (int i = 0; i < a.length; i += 1) {
			a[i] = ((int)(Math.random()*size)); //avg
//			a[i] = i; //best
			System.out.print(a[i] + " ");
		}
		System.out.println();		

		sort(a, 0, a.length - 1);

		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
		System.out.println();
	}


	
	public static void sort(int a[], int lower, int upper) {
		if (lower < upper) {
			int middle = (lower + upper) / 2;
			sort(a, lower, middle);
			sort(a, middle + 1, upper);
			merge(a, lower, upper);
		}
	}
	
	public static void merge(int a[], int lower, int upperEnd) {
		int lowerEnd = (lower + upperEnd) / 2;
		int upper = lowerEnd + 1;
		int tmp = lower;
		int numElements = upperEnd - lower + 1;
		int tmpArray[] = new int[a.length];
		
		while (lower <= lowerEnd && upper <= upperEnd) {
			if (a[lower] < (a[upper])) {
				tmpArray[tmp++] = a[lower++];
			} else {
				tmpArray[tmp++] = a[upper++];
			}

		}
		while (lower <= lowerEnd) {
			tmpArray[tmp++] = a[lower++];
		}
		while (upper <= upperEnd) {
			tmpArray[tmp++] = a[upper++];
		}
		for (int i = 0; i < numElements; i++,upperEnd--) {
			a[upperEnd] = tmpArray[upperEnd];
		}
	}
	
}