一、定义
归并排序分为两种：
“自顶向下”的归并排序。
该类归并排序是算法设计中“分治”思想的典型应用。
其实就是将数组分为两部分，然后递归地将两部分分别排序，将排序后的两个数组进行归并。“自底向上”的归并排序。
该类归并排序是先两两归并size=1的小数组，形成size=2的各对数组；然后再两两归并size=2数组，直到归并size=N的大数组。
“自底向上”不需要用到递归，适合以链表形式组织的数据。
二、实现
2.1 自顶向下的归并排序
2.1.1 基本思想
将数组分为2部分，递归对每部分进行排序后，再将2部分进行归并。
2-1-1 自顶向下的示意图
2.1.2 运行轨迹
运行轨迹示意图：
2-1-2 运行轨迹图
2-1-3 递归调用图
2.1.3 源码
public class Merge {
public static void sort(Comparable[] a) {
// 辅助数组，用于归并（此处未用原地归并）
Comparable[] aux = new Comparable[a.length];
sort(a, aux, 0, a.length - 1);
assert isSorted(a);
}
// mergesort a[lo..hi] using auxiliary array aux[lo..hi]
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
if (hi <= lo)
return;
int mid = lo + (hi - lo) / 2;
// 对a[lo,mid]进行归并排序
sort(a, aux, lo, mid);
// 对a[mid+1,hi]进行归并排序
sort(a, aux, mid + 1, hi);
// 对已经有序的a[lo .. mid] 和 a[mid+1 ..hi] 进行归并
merge(a, aux, lo, mid, hi);
}
}
2.2 自底向上的归并排序
2.2.1 基本思想
“自底向上”的归并排序不需要用到递归，而是采用两两归并的方式，将小数组逐渐归并成大数组，具体步骤如下：
- 首先对size=1的数组进行两两归并，得到size=2的数组；
- 对size=2的数组进行两两归并，得到size=4的数组；
- 依次类推，直到对size=N的数组归并完成。
2.2.2 运行轨迹
如下图所示，“自底向上”的归并排序会多次遍历整个数组，根据子数组的大小进行两两归并。
子数组的大小sz初始值为1，每次加倍。最后一个子数组的大小只有在数组大小是偶数倍的时候才会等于sz（否则会比sz小）。
2-2-2 运行轨迹图
2.2.3 源码
public static void sort(Comparable[] a) {
int N = a.length;
Comparable[] aux = new Comparable[N]; // 辅助数组，用于归并（此处未用原地归并）
for (int sz = 1; sz < N; sz *= 2) { // sz表示待归并的子数组大小
for (int lo = 0; lo < N - sz; lo += sz + sz) {
int mid = lo + sz - 1;
int hi = Math.min(lo + sz + sz - 1, N - 1);
merge(a, aux, lo, mid, hi); // 对a[lo,mid]和a[mid+1,hi]进行归并
}
}
assert isSorted(a);
}
三、原地归并
归并排序的难点在于如何将两个有序数组进行原地归并。
通常情况下，如果不进行原地归并，需要一个大小为N的辅助数组。
3.1 原地归并的思想
原地归并排序运用了“内存反转”的思想（也称为手摇算法），具体可以参见《编程珠玑》。
原地归并关键在于merge这个归并函数，步骤如下：
- 初始时，两段分别递增的子数组
arr[begin…mid]和arr[mid+1…end]。i=begin，j=mid+1
原则：始终保证指针i之前的元素为两个序列中最小的那些元素，即i之前为已经归并好的元素。
-
i往后移动，找到第一个arr[i]>arr[j]的索引
- j往后移动，再找第一个
arr[j]>arr[i]的索引。
此时arr[begin…i-1]序列是整个数组的最小序列；arr[mid+1…j-1]序列是整个数组的次小序列。 - 将
arr[i…mid]的内存块和arr[mid+1…j-1]的内存块对调，这样较小的部分就调到前面去了。
对调方法（手摇算法）：先reverse(arr[i…mid])，再reverse(arr[mid+1…j-1])，最后reverse(arr[i…j-1])
- 之后，
i=i + j - mid - 2，mid=j-1，a[i，mid]和a[j，end]又是两个递增的子数组，继续迭代即可。
3.2 源码
public class Merge {
/**
* 原地归并
* <P>
* arr[begin,mid],arr[mid+1,end]为分别递增有序的子数组
* <P>
*/
public static void merge(int[] arr, int begin, int mid, int end) {
int i = begin, j = mid + 1;
while (i < j && j <= end) {
// 找到第一个arr[i]>=arr[j]的索引
while (i <= mid && arr[i] < arr[j]) {
i++;
}
// 找到第一个arr[j]>=arr[i]的索引
while (j <= end && arr[j] < arr[i]) {
j++;
}
if (i == j)
break;
// 将arr[i…mid]的内存块和arr[mid+1…j-1]的内存块对调
swapBlock(arr, i, mid, mid + 1, j - 1);
i = i + j - mid - 2;
mid = j - 1;
}
}
private static void swapBlock(int[] arr, int i, int mid, int j, int k) {
reverse(arr, i, mid); // 逆序arr[i…mid]
reverse(arr, j, k); // 逆序arr[j…k]
reverse(arr, i, k); // 逆序arr[i…k]
}
private static void reverse(int[] arr, int i, int k) {
// TODO Auto-generated method stub
}
}
四、性能分析
- 时间复杂度
最坏情况下，为O(NlogN) - 空间复杂度
当使用辅助数组进行归并时为O(N)，原地归并不需要额外空间
