package edu.mit.ita.util;

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) {
        // Trivially sorted
        if (seq == null || seq.length <= 1) {
            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 (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);
    }

    // Precondition: seq[lo..mid] and seq[mid+1..hi] must be sorted
    private static <T extends Comparable<? super T>> void merge(T[] seq, T[] auxSeq, int lo, int mid, int hi) {
        System.arraycopy(seq, lo, auxSeq, lo, hi - lo + 1);

        int i = lo;
        int j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                seq[k] = auxSeq[j++];
            } else if (j > hi) {
                seq[k] = auxSeq[i++];
            } else if (lt(auxSeq[i], auxSeq[j])) {
                seq[k] = auxSeq[i++];
            } else {
                seq[k] = auxSeq[j++];
            }
        }
    }
}

@@ -952,105 +952,69 @@
     
-System.arraycopy(seq, lo, auxSeq, lo, hi - lo + 1);%0A%0A        int i = lo;%0A        int j = mid + 1;
+int i, j, k;%0A%0A        // Copy seq%5Blo..mid%5D to auxSeq%5Blo..mid%5D
 %0A   
@@ -1024,18 +1024,22 @@
   for (i
-nt
+ = lo,
  k = lo;
@@ -1043,16 +1043,22 @@
 lo; 
-k
+i
  %3C= 
-hi;
+mid; i++,
  k++
@@ -1077,36 +1077,47 @@
     
-if (i %3E mid) %7B%0A
+auxSeq%5Bk%5D = seq%5Bi%5D;%0A   
      
+%7D%0A%0A
         
    s
@@ -1116,122 +1116,286 @@
     
-   seq%5Bk%5D = auxSeq%5Bj++%5D;%0A            %7D else if (j %3E hi) %7B%0A                seq%5Bk%5D = auxSeq%5Bi++%5D;%0A            %7D else
+// Reverse copy seq%5Bhi..mid+1%5D to auxSeq%5Bmid+1..hi%5D%0A        for (j = hi; j %3E mid; j--, k++) %7B%0A            auxSeq%5Bk%5D = seq%5Bj%5D;%0A        %7D%0A%0A        // Merge auxSeq%5Blo..mid%5D and auxSeq%5Bhi..mid+1%5D back into seq%5Blo..hi%5D%0A        for (i = lo, j = hi, k = lo; k %3C= hi; k++) %7B%0A           
  if 
@@ -1515,18 +1515,18 @@
 auxSeq%5Bj
-++
+--
 %5D;%0A     

improve merge part of merge sort