共计 2757 个字符，预计需要花费 7 分钟才能阅读完成。
前言
本周讲解两个 50 多年前发明，但今天仍然很重要的经典算法 (归并排序和快速排序) 之一 — 归并排序，几乎每个软件系统中都可以找到其中一个或两个的实现，并研究这些经典方法的新变革。我们的涉及范围从数学模型中解释为什么这些方法有效到使这些算法适应现代系统的实际应用的细节。
Mergesort。我们研究 mergesort 算法，并证明它保证对 n 项的任何数组进行排序，最多只能进行 nlgn 次的比较。我们还考虑一个非递归的自下而上版本。我们证明，在最坏的情况下，任何基于比较的排序算法必须至少进行 ~nlgn 的比较。我们讨论对我们正在排序的对象使用不同的排序以及相关的稳定性概念。
上一篇：基本数据类型下一篇：快速排序
这章我们讨论归并排序，这是计算基础中的两个重要排序算法之一我们已经对一些算法有了科学全面的认知，这些算法被大量运用在系统排序和应用内排序超过 50 多年，我们之后所要看到的快速排序更是被在科学和工程中被誉为 20 世纪 10 大算法之一
归并排序
概貌
所以归并排序到底是什么样的?
基本计划流程：
将阵列分成两半
递归排序每一半
合并两半
它的思想其实很简单, 只要把数组一分为二, 然后再不断将小数组递归地一分为二下去, 经过一些排序再将它们合并起来, 这就是归并排序的大致思想, 这是人们在计算机上实现的最早的算法之一.(EDVAC 计算机是最早的通用型计算机之一, 冯诺依曼认为在他的 EDVAC 中需要一种排序算法, 于是他提出了归并排序, 因此他被公认为是归并排序之父)
归并排序的核心就是“并”。所以要理解如何归并，先考虑一种抽象的“原位归并”。
抽象合并演示
目标 给定一个数组，它的前一半 (a[lo]-[mid]) 和 后一半 ([mid + 1]-[hi]) 已是排好序的，我们所要做的就是将这两个子数组合并成一个大的排好序的数组
看一个演示
1. 在排序之前我们需要一个辅助数组，用于记录数据，这是实现归并的最简单的方式
2. 首先将原数组中所有东西拷贝进辅助数组，之后我们就要以排好的顺序将它们拷贝回原数组这时我们需要三个下标：i 用于指向左边子数组；j 指向右边子数组；k 指向原数组即排好序的数组。
3. 首先取 i 和 j 所指数字中取其中小的放入原数组 k 的位置，当一个被拿走之后，拿走位置的指针 (这次是 j) 和 k 递增
4. 同样取 i 和 j 中小的那个移向 k 的位置，再同时增加移动位置的指针 (这次还是 j 和 k)
以此类推。完整演示地址：在此这就是一种归并方式：用了一个辅助数组，将它们移出来又排好序放回去。这就是归并部分的代码，完全依着之前的演示
Java 实现
public class Merge {
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
/**
* assertion 功能: 方便我们找出漏洞并且确定算法的正确
* 想确定 a[lo] 到 a[mid] 和 a[mid+1] 到 a[hi] 是否已是排好序的
*/
assert isSorted(a, lo, mid);
assert isSorted(a, mid + 1, hi);
// 拷贝所有东西进辅助数组
for (int k = lo; k <= hi; k++)
aux[k] = a[k];
/**
* 完成归并
* 初始化 i 在左半边的最左端
* j 在右半边最左端
* 指针 k 从 lo 开始
* 比较辅助数组中 i 和 j 谁更小，并将小的那个的值移向 k
**/
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
// 如果 i 走到边界了，就只将 j 的值都移上去
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++];
}
// 最后再检查最终合并后的时候排好序
assert isSorted(a, lo, hi);
}
// 递归的 sort 方法
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);
}
// 对外提供接口中 sort 函数
public static void sort(Comparable[] a) {
// 创建辅助数组
Comparable[] aux = new Comparable[a.length];
sort(a, aux, 0, a.length – 1);
}
}
在这个简单的实现中传入了 Comparable 类型的原数组 a[] 和 辅助数组 aux[], 还有三个参数 lo, mid, and hi. lo 指向的是两个将要合并的子数组的头部 mid 指向前一个子数组的末端 所以我们的前提是 lo 到 mid 时排好的 从 mid+ 1 到 hi 也是排好的
有了归并，排序中递归的就简单多了。sort() 在递归调用前先检查下标，然后像二分查找那样计算中点值。sort 前半部分，再 sort 后半部分，然后 merge 对外提供接口中 sort 函数只接收一个参数，创建辅助数组的任务就交给这个 sort()
这里关键在于不要将辅助数组在递归的 sort() 中创建, 因为那会多出许多额外的小数组的花费, 如果一个归并排序效率很低通常都是由这引起 这是一个很直接的实现方式。也是依据了我们看到多次的一个思想 – 分治法：即解决问题时将其一分为二，分别解决两个小问题，再将它们合并起来
Assertion
一般来说 Java 程序员，认为加入这些 assert 是有益的：1. 帮助我们发现漏洞 2. 同时也提示了之间的代码的功能这个归并代码就是很好的例子，如此以代码的形式加入 assert 语句表明了接下来你想做什么，在代码最后加上 assert 语句表明了你做了什么。你不仅确定了代码的正确，也告诉阅读代码的人你所干的事情。
Java 中 asset 语句接受一个 boolean 值。isSorted 函数前面已经写过了 (请回复 — 基本排序)，如果排好序返回 true，反之返回 false. assert 在验证到没正确排序时会抛出异常.
assert 可以在运行时禁用. 这很有用因为你可以把 asset 语句一直放在代码中, 编程时供自己所需, 禁用后在最终上线程序中不会有额外代码。因此 assertion 默认是禁用的。出错的时候人们还可以启用 assertion 然后找到错误所在。
java -ea MyProgram // 启用 assertions
java -da MyProgram // 禁用 assertions(默认)
所以平时最好像之前的例子那样加入 assert 语句，并且不让他们出现在产品代码中，而且不要用额外的参数来做检查。
算法分析
附录