关键代码实现：
private static void merge(Comparable[] input, int lo, int mid, int hi) { //copy input[lo,mid] to aux[lo,mid] for(int i = lo; i <= mid; i++) { aux[i] = input[i]; } //copy input[mid+1,hi] to aux[hi,mid+1] for(int i = mid+1; i <= hi; i++) { aux[i] = input[hi-i+mid+1]; } int i = lo; int j = hi; for(int k = lo; k <= hi; k++) { 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 }
分析：
当j从hi减到mid的时候，less(aux[j],aux[i])永为false，则一直执行input[k] = aux[i++]。
当i从lo增至mid+1时，less(aux[j],aux[i])永为true，则一直执行input[k] = aux[j--]。
所以可以移除索引i和j出界判断的代码。
测试结果：
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, 4, 5)E G M R E S O R T E X A M P L E merge(input, 6, 6, 7)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, 12, 12, 13)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.4s FasterMerge is 3.1s