private static void sort(Comparable[] input, int lo, int hi) {

        if(lo >= hi)//just one entry in array

            return;

        int mid = lo + (hi-lo)/2;

        sort(input, lo, mid);

        sort(input, mid+1, hi);

        if(!less(input[mid+1],input[mid]))//input[mid+1] >= input[mid]

            return;

        merge(input, lo, mid, hi);

    }

package com.qiusongde;

import edu.princeton.cs.algs4.In;

import edu.princeton.cs.algs4.StdOut;

public class MergeSkipMerge {

    private static Comparable[] aux;

    public static void sort(Comparable[] input) {

        int N = input.length;

        aux = new Comparable[N];

        sort(input, 0, N-1);

    }

    private static void sort(Comparable[] input, int lo, int hi) {

        if(lo >= hi)//just one entry in array

            return;

        int mid = lo + (hi-lo)/2;

        sort(input, lo, mid);

        sort(input, mid+1, hi);

        if(!less(input[mid+1],input[mid]))//input[mid+1] >= input[mid]

            return;

        merge(input, lo, mid, hi);

    }

    private static void merge(Comparable[] input, int lo, int mid, int hi) {

        //copy input[lo,hi] to aux[lo,hi]

        for(int i = lo; i <= hi; i++) {

            aux[i] = input[i];

        }

        int i = lo;

        int j = mid + 1;

        for(int k = lo; k <= hi; k++) {

            if(i > mid)

                input[k] = aux[j++];

            else if(j > hi)

                input[k] = aux[i++];

            else if(less(aux[j], aux[i]))

                input[k] = aux[j++];

            else

                input[k] = aux[i++];

        }

        StdOut.printf("merge(input, %4d, %4d, %4d)", lo, mid, hi);

        show(input);//for test

    }

    private static boolean less(Comparable v, Comparable w) {

        return v.compareTo(w) < 0;

    }

    private static void show(Comparable[] a) {

        //print the array, on a single line.

        for(int i = 0; i < a.length; i++) {

            StdOut.print(a[i] + " ");

        }

        StdOut.println();

    }

    public static boolean isSorted(Comparable[] a) {

        for(int i = 1; i < a.length; i++) {

            if(less(a[i], a[i-1]))

                return false;

        }

        return true;

    }

    public static void main(String[] args) {

        //Read strings from standard input, sort them, and print.

        String[] input = In.readStrings();

        show(input);//for test

        sort(input);

        assert isSorted(input);

        show(input);//for test

    }

}

M E R G E S O R T E X A M P L E

merge(input,    0,    0,    1)E M R G E S O R T E X A M P L E

merge(input,    2,    2,    3)E M G R E S O R T E X A M P L E

merge(input,    0,    1,    3)E G M R E S O R T E X A M P L E

merge(input,    4,    5,    7)E G M R E O R S T E X A M P L E

merge(input,    0,    3,    7)E E G M O R R S T E X A M P L E

merge(input,    8,    8,    9)E E G M O R R S E T X A M P L E

merge(input,   10,   10,   11)E E G M O R R S E T A X M P L E

merge(input,    8,    9,   11)E E G M O R R S A E T X M P L E

merge(input,   14,   14,   15)E E G M O R R S A E T X M P E L

merge(input,   12,   13,   15)E E G M O R R S A E T X E L M P

merge(input,    8,   11,   15)E E G M O R R S A E E L M P T X

merge(input,    0,    7,   15)A E E E E G L M M O P R R S T X

A E E E E G L M M O P R R S T X 

For 20000 random Doubles 1000 trials

Merge is 3.6s MergeFasterM is 3.3s MergeUseInsert is 3.2s MergeSkipMerge is 3.4s