package edu.mit.ita.util;

import static edu.mit.ita.util.Arrays.isSorted;
import static edu.mit.ita.util.Arrays.isTriviallySorted;
import static edu.mit.ita.util.Comparables.lt;

final class MergeSort {
    private MergeSort() {
    }

    @SuppressWarnings("unchecked")
    static <T extends Comparable<? super T>> void sort(T[] seq) {
        if (isTriviallySorted(seq)) return;

        T[] auxSeq = (T[])new Comparable<?>[seq.length];
        sort(seq, auxSeq, 0, seq.length - 1);
    }

    private static <T extends Comparable<? super T>> void sort(T[] seq, T[] auxSeq, int lo, int hi) {
        if (isTriviallySorted(seq, lo, hi)) return;

        int mid = lo + (hi - lo) / 2;
        sort(seq, auxSeq, lo, mid);
        sort(seq, auxSeq, mid + 1, hi);
        merge(seq, auxSeq, lo, mid, hi);
    }

    private static <T extends Comparable<? super T>> void merge(T[] seq, T[] auxSeq, int lo, int mid, int hi) {
        assert isSorted(seq, lo, mid);
        assert isSorted(seq, mid + 1, hi);

        // Copy seq[lo..mid] to auxSeq[lo..mid] and seq[hi..mid+1] to auxSeq[mid+1..hi]
        int i = lo, j = hi, k = lo;
        while (i <= mid) auxSeq[k++] = seq[i++];
        while (j > mid) auxSeq[k++] = seq[j--];

        // Merge (in sorted order) auxSeq[lo..mid] and auxSeq[hi..mid+1] into seq[lo..hi]
        for (i = lo, j = hi, k = lo; k <= hi; k++) {
            if (lt(auxSeq[i], auxSeq[j])) {
                seq[k] = auxSeq[i++];
            } else {
                seq[k] = auxSeq[j--];
            }
        }
    }
}

@@ -176,32 +176,144 @@
 lt;%0A
-%0Afinal class MergeSort %7B
+import static edu.mit.ita.util.SortMethods.insertionSort;%0A%0Afinal class MergeSort %7B%0A    private static final int ALT_SORT_THRESHOLD = 7;%0A
 %0A   
@@ -791,33 +791,37 @@
 o) / 2;%0A        
-s
+bestS
 ort(seq, auxSeq,
@@ -831,33 +831,37 @@
 , mid);%0A        
-s
+bestS
 ort(seq, auxSeq,
@@ -915,32 +915,329 @@
 id, hi);%0A    %7D%0A%0A
+    private static %3CT extends Comparable%3C? super T%3E%3E void bestSort(T%5B%5D seq, T%5B%5D auxSeq, int lo, int hi) %7B%0A        int elementsToSort = hi - lo + 1;%0A        if (elementsToSort %3E= ALT_SORT_THRESHOLD)%0A            insertionSort(seq, lo, hi);%0A        else%0A            sort(seq, auxSeq, lo, hi);%0A    %7D%0A%0A
     private stat
@@ -1821,18 +1821,16 @@
 Seq%5Bj%5D))
- %7B
 %0A       
@@ -1875,17 +1875,13 @@
     
- %7D
  else
- %7B
 %0A   
@@ -1919,22 +1919,8 @@
 -%5D;%0A
-            %7D%0A
     

improve merge sort by delegating to insertion sort for small sequences