private void sort(int input[], int low, int high){
        if(low >= high){
            return;
        }
        
        int middle = (low + high)/2;
        sort(input, low, middle);
        sort(input, middle+1, high);
        sortedMerge(input,low,high);
   }
http://en.wikipedia.org/wiki/Merge_sort
Test cases
1 element
2 element
negative numbers
already sorted
reverse sorted
src/com/interview/sort/MergeSort.java