归并排序及其优化

归并排序的核心在于如何合并两个有序序列，即merge方法的实现。我们可以借助一个辅助数组aux，第一步将原序列a[lo..hi]复制到aux当中，第二步再将aux归并回原数组。merge方法代码如下：

private void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
        //把a[lo..hi]复制到aux[lo..hi]
        int i = lo;
        int j =mid+1;
        if (hi + 1 - lo >= 0)
            System.arraycopy(a, lo, aux, lo, hi + 1 - lo);
        //aux[lo..hi]归并回a[lo..hi]
        for (int k=lo;k<=hi;k++) {
            if (i>mid) a[k] = aux[j++]; //左半边用尽
            else if (j>hi) a[k] = aux[i++]; //右半边用尽
            else if (less(aux[j], aux[i])) a[k] = aux[j++]; //右半边当前元素小于左半边当前元素
            else a[k] = aux[i++]; //右半边当前元素大于等于左半边当前元素
        }
    }
//比较元素的less方法
private static boolean less(Comparable v, Comparable w) {
        if (v == w) return false;   // optimization when reference equals
        return v.compareTo(w) < 0;
    }

merge方法完成后，归并排序的步骤就很清晰了：

1. 将左半边 a[lo..mid] 排序；
2. 将右半边 a[mid+1..hi] 排序
3. 归并结果

public void sort(Comparable[] a) {
                //创建辅助数组
        Comparable[] aux = new Comparable[a.length];
        sort2(a, aux, 0, a.length-1);
    }

private void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        merge(a, aux, lo, mid, hi);
    }

归并排序的迭代算法，从大小为1的序列开始，二二合并，四四合并，八八合并。。。

public void sortBU(Comparable[] a) {
        int n = a.length;
        Comparable[] aux = new Comparable[n];
        for (int sz=1;sz<n;sz = sz+sz) //sz子数组大小以2的幂增加
            for (int lo=0;lo<n-sz;lo += sz+sz) //lo:子数组索引
                merge(a, aux, lo, lo+sz-1, Math.min(lo+sz+sz-1, n-1)); //merge方法同上
    }

以上归并排序还有可以优化的地方，在此提三点优化方案：

1. 归并排序的递归在处理小规模问题时会使方法调用过于频繁，可以使用插入排序处理小规模的排序（hi - lo <=7），排序效率可以得到提升。

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
        // if (hi <= lo) return;
        //小规模排序使用插入排序,CUTOFF = 7
        if (hi <= lo + CUTOFF) {
            insertionSort(dst, lo, hi);
            return;
        }
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid+1, hi);
        merge(a, aux, lo, mid, hi);
    }

2. 如果序列已经有序，那么后面的合并就没必要执行，当a[mid] <= a[mid+1]时，跳过merge方法。

private void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        //判断条件，用来提前终止merge动作
        if (!less(a[mid+1], a[mid])) return;
        merge(a, aux, lo, mid, hi);
    }

3. 可以节省将数组元素复制到辅助数组所用的时间，具体做法是交替调用两种归并方法，一种是将原数组排序到辅助数组，一种是将辅助数组排序到原数组。

//该方法不再复制数组的元素，而是直接将src数组的元素归并到dst数组
private static void merge(Comparable[] src, Comparable[] dst, int lo, int mid, int hi) {
        int i = lo, j = mid+1;
        for (int k = lo; k <= hi; k++) {
            if      (i > mid)              dst[k] = src[j++];
            else if (j > hi)               dst[k] = src[i++];
            else if (less(src[j], src[i])) dst[k] = src[j++];   // to ensure stability
            else                           dst[k] = src[i++];
        }
    }

 private static void sort(Comparable[] src, Comparable[] dst, int lo, int hi) {
        if (hi <= lo + CUTOFF) {
            insertionSort(dst, lo, hi);
            return;
        }
        int mid = lo + (hi - lo) / 2;
        //注意这里，将dst和src位置换了，递归的每一层两个数组都交换一次位置
        sort(dst, src, lo, mid);
        sort(dst, src, mid+1, hi);
        // using System.arraycopy() is a bit faster than the above loop
        if (!less(src[mid+1], src[mid])) {
            System.arraycopy(src, lo, dst, lo, hi - lo + 1);
            return;
        }
        merge(src, dst, lo, mid, hi);
    }

参考书目:
Algorithms Fourth Edition

参考代码:
自顶而下归并
自底而上归并
归并的三种优化