// Divide and conquer strategy.
// 1.	Divide the unsorted list into two sublists of about half the size.
// 2.	Divide each of the two sublists recursively until we have list sizes of length 1, in which case the list itself is returned.
// 3.	Merge the two sublists back into one sorted list. - Show diagram.
// Improved runtime because:
// 1.	A small list will take fewer steps to sort than a large list.
// 2.	Fewer steps are required to construct a sorted list from two sorted lists than two unsorted lists.

// Average and worst case performance - n log n comparisons
 
public class MergeSort {
	private static int comparisonCount = 0;
	
	public static void main(String[] args) {
		for (int i = 0; i < args.length; i++) {
			System.out.print(args[i] + " ");
		}
		System.out.println();
		String[] results = doMergeSort(args, 0, args.length - 1);
		System.out.println("Comparison Count: " + comparisonCount);
		System.out.println();
		for (int i = 0; i < results.length; i++) {
			System.out.print(results[i] + " ");
		}
	}
	
	public static String[] doMergeSort(String[] list, int start, int end) {
    		if (end == start) {
    			return new String[] {list[start]};
    		} else if (end < start) {
    			return new String[] {};
    		}

	    	int middle = (end + start) / 2;
	  	String[] leftList = doMergeSort(list, start, middle);
	    	String[] rightList = doMergeSort(list, middle + 1, end);
	    	return merge(leftList, rightList);
	}

	public static String[] merge(String[] leftList, String[] rightList) {
		String[] result = new String[leftList.length + rightList.length];
		int left = 0, right = 0, resultIndex = 0;
		while (left < leftList.length && right < rightList.length) {
			if (leftList[left].compareTo(rightList[right]) <= 0) { 
				result[resultIndex++] = leftList[left++];
			} else {
				result[resultIndex++] = rightList[right++];
			}
			comparisonCount++;
		}
    		while (left < leftList.length) { 
    			result[resultIndex++] = leftList[left++];
    		}
    		while (right < rightList.length) {
    			result[resultIndex++] = rightList[right++];
    		}
    		return result;
	}

}