归并操作指将两个有序的数组归并成一个更大的有序数组。要将一个数组排序，可以先（递归的）将它分成两半分别排序，然后将结果归并起来。归并排序最吸引人的性质就是它能够保证将任意长度为N的数组排序所需时间和NlogN成正比。主要缺点是它所需要的额外空间和N成正比。
image.png
- 原地归并的抽象方法
实现归并的一种直截了当的方法是将两个不同的有序数组归并到第三个数组中。
private void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// 复制到 aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
// 归并到 a[]
int i = lo, j = mid+1;
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++];
}
}
- 自顶向下的归并排序
基于原地归并的抽象实现的另一种递归归并，高效应用分治思想的典型例子。
如果它能将两个子数组排序，它就能够通过归并两个子数组来讲数组排序
public static void mergeSort(Comparable[] a) {
Comparable[] aux = new Comparable[a.length];
sort(a,aux,0,a.length-1);
}
private static 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); //上文中的原地归并
}
// 具体类中 aux 可是全局变量
image.png
- 自底向上的归并排序
先归并那些微型数组，然后再成对归并得到子数组，直到我们将整个数组归并在一起。首先我们进行的是两两归并（把每个元素想象成一个大小为1的数组），然后四四归并（两个大小为2 的数组归并成一个有4个元素的数组），然后八八归并，....
void mergeBUSort(Comparable[] a) {
int n = a.length;
Comparable[] aux = new Comparable[n];
for (int len = 1; len < n; len *= 2) { // 1 2 4 8 ....
for (int lo = 0; lo < n-len; lo += len+len) { // 子数组的大小初始值为1，每次加倍
int mid = lo+len-1;
int hi = Math.min(lo+len+len-1, n-1);
merge(a, aux, lo, mid, hi);
}
}
}
image.png
