public class MergeSort {

	// assumes a[start]...a[mid-1] is sorted and a[mid]...a[end-1] is sorted
	// makes start to end-1 sorted by merging the two lists
	private static <T extends Comparable<? super T>> void merge(T [] a, int start, int mid, int end, T[] temp) {
		int firstListIndex=start, secondListIndex=mid, mergedListIndex=0;
		
		// merge until one of the lists runs out
		while(firstListIndex<mid && secondListIndex<end) {
			if(a[firstListIndex].compareTo(a[secondListIndex])<0)
				temp[mergedListIndex++]=a[firstListIndex++];
			else
				temp[mergedListIndex++]=a[secondListIndex++];
		}
		
		// bring over the tails
		while(firstListIndex<mid) 
			temp[mergedListIndex++]=a[firstListIndex++];
		
		while(secondListIndex<end) 
			temp[mergedListIndex++]=a[secondListIndex++];
		
		// move things back from temp into a, now merged
		for (int i=start; i<end;  i++)
			a[i]=temp[i-start];
	}
	// Sorts entries from a[start] to a[end-1]
	private static <T extends Comparable<? super T>> void sortHelper(T [] a, int start, int end, T[] temp) {
		if(end-start>=2) { //it may be worth it to have a higher base case in order to speed things up by running insertionSort when the array is small enough
			int mid = (end+start)/2;
			sortHelper(a, start, mid, temp);
			sortHelper(a, mid, end, temp);
			merge(a, start, mid, end, temp);
		}
	}
	
	public static <T extends Comparable<? super T>> void sort(T [] a) {
		T [] temp = (T[]) new Comparable [a.length]; // merging into temp
		sortHelper(a, 0, a.length, temp);
	}

	public static void main(String[] args) {
		Integer [] a={10, 6, 15, 7, 8, 2, 6, 7, 2, 0};
		sort(a);
		for(Integer x : a) // for each element x in the array a
			System.out.print(x+" ");

	}

}