title: merge sort with insertion sort
body: <p>I was implementing a merge sort in <a href="http://algs4.cs.princeton.edu/lectures/22Mergesort.pdf" rel="nofollow">Algorithms in Java 4th edition</a>.
  My basic merge sort works, and I want to improve the algorithm by using insertion sort when the array size is less than 7.
  I thought it is obvious an efficient improvement, but actually the original one is faster than the improved one for large data.</p>
  
  <p>Here is my improved merge sort, CUTOFF = 7:</p>
  
  <pre><code>private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
  
    // Copy to aux[]
    for (int i = lo; i &lt;= hi; i++) {
      aux[i] = a[i];
    }
  
    // Merge back to a[]
    int i = lo, j = mid + 1;
    for (int k = lo; k &lt;= hi; k++) {
      if      (i &gt; mid)              a[k] = aux[j++];
      else if (j &gt; hi)               a[k] = aux[i++];
      else if (less(aux[i], aux[j])) a[k] = aux[i++];
      else                           a[k] = aux[j++];
    }
  }
  
  private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
  
    // #1 improvement
    // Stop condition for this recursion.
    // This time we add a CUTOFF, when the items in array
    // is less than 7, we will use insertion sort.
    if (hi &lt;= lo + CUTOFF - 1) {
      Insertion.sort(a, lo, hi);
      return;
    }
  
    int mid = lo + (hi - lo) / 2;
    sort(a, aux, lo, mid);
    sort(a, aux, mid + 1, hi);
    if (!less(a[mid+1], a[mid])) return;
    merge(a, aux, lo, mid, hi);
  }
  
  public static void sort(Comparable[] a) {
    Comparable[] aux = new Comparable[a.length];
    sort(a, aux, 0, a.length - 1);
  }
  </code></pre>
  
  <p>The insertion sort code:</p>
  
  <pre><code>public static void sort(Comparable[] a, int lo, int hi) {
    for (int i = lo; i &lt;= hi; i++) {
      for (int j = i; j &gt; 0 &amp;&amp; less(a[j], a[j - 1]); j--) {
        exch(a, j, j - 1);
      }
    }
  }
  </code></pre>
  
  <p>I used a SortCompare.java to compare the execute time:</p>
  
  <pre><code>public class SortCompare {
  
    public static double time(String alg, Comparable[] a) {
      Stopwatch timer = new Stopwatch();
      if (alg.equals("Insertion")) Insertion.sort(a);
      if (alg.equals("Selection")) Selection.sort(a);
      if (alg.equals("Shell")) Shell.sort(a);
      if (alg.equals("Merge")) Merge.sort(a);
      if (alg.equals("MergeWithImprovements")) MergeWithImprovements.sort(a);
      //if (alg.equals("Quick")) Quick.sort(a);
      //if (alg.equals("Heap")) Heap.sort(a);
      if (alg.equals("InsertionWithSentinel")) InsertionWithSentinel.sort(a);
      return timer.elapsedTime();
    }
  
    public static double timeRandomInput(String alg, int N, int T) {
      // Use alg to sort T random arrays of length N.
      double total = 0.0;
      Double[] a = new Double[N];
      for (int t = 0; t &lt; T; t++) {
        for (int i = 0; i &lt; N; i++) {
          a[i] = StdRandom.uniform();
        }
        total += time(alg, a);
      }
      return total;
    }
  
    public static void main(String[] args) {
      String alg1 = args[0];
      String alg2 = args[1];
      int N = Integer.parseInt(args[2]);
      int T = Integer.parseInt(args[3]);
      double t1 = timeRandomInput(alg1, N, T);  // Total for alg1
      double t2 = timeRandomInput(alg2, N, T);
      StdOut.printf("For %d random Doubles\n   %s is", N, alg1);
      StdOut.printf(" %.1f times faster than %s\n", t2/t1, alg2);
    }
  }
  </code></pre>
  
  <p>I generated 100 arrays with 10000 elements each. The original merge sort is 30 times faster than the improved one!</p>