归并排序的核心在于如何合并两个有序序列，即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方法完成后，归并排序的步骤就很清晰了：
- 将左半边 a[lo..mid] 排序；
- 将右半边 a[mid+1..hi] 排序
- 归并结果
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方法同上
}
以上归并排序还有可以优化的地方，在此提三点优化方案：
- 归并排序的递归在处理小规模问题时会使方法调用过于频繁，可以使用插入排序处理小规模的排序（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);
}
- 如果序列已经有序，那么后面的合并就没必要执行，当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);
}
- 可以节省将数组元素复制到辅助数组所用的时间，具体做法是交替调用两种归并方法，一种是将原数组排序到辅助数组，一种是将辅助数组排序到原数组。
//该方法不再复制数组的元素，而是直接将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);
}
