00 Introduction

待排序的内容超过了计算机高速内部存储器（内存等）的容量【以下用内存来表示内部存储器】，出现一些有趣的问题。外部排序和内部排序差别很大，因为外部存储（SSD，HDD等）和内存的性质有很大的不同。内部排序算法（插入、选择排序等）对于外部排序是无用的。

假设有 500 万个记录， $R_1,R_2,\cdots,R_{5,000,000}$ 。内存一次只能放下 100 万个记录进行排序，那么如何对这 500 万个记录排序呢？

一个很明显的做法是分组排序，分成五个子文件，每个排序完成之后，合并有序的文件。而合并有序文件就可以使用很简单的线性数据结构完成了。

先内排再外排这个思路是普遍适用的，后面集中讨论外排。

串（string）往往指任意序列。我们用有序顺串或顺串（run）来表示排序好的部分。

考虑平衡的两路合并，我们使用四个磁带（tape）进行外排。内部排序输出的各个顺串交替的放到磁带 1 和磁带 2 上。然后磁带 1 和磁带 2 绕回开始的位置，每个磁带取出一个顺串，合并，得到一个长度两倍的顺串，这些顺串交替的放到磁带 3 和磁带 4 上。如果磁带 1 比磁带 2 的顺串多，那么磁带 2 后面增加一个长度为 0 的虚假（dummy）的顺串就好。反复操作，直到只剩下一个顺串。

如果内排产生了 $2^{k-1}<S\leq 2^k$ 个顺串，那么平衡的两路合并需要 $k=\lceil \lg S\rceil$ 次合并扫描。

比如上面的例子， $S=5$ ，每次排序 100 万个记录。那么内排完成后数据如下


磁带 1	$R_1\cdots R_{1,000,000};R_{2,000,001}\cdots R_{3,000,000};R_{4,000,001}\cdots R_{5,000,000}$
磁带 2	$R_{1,000,001}\cdots R_{2,000,000};R_{3,000,001}\cdots R_{4,000,000}$
磁带 3
磁带 4

第一次合并扫描，读取磁带 1 和磁带 2，合并的更长的顺串放到磁带 3 和磁带 4 上。磁带 2 比磁带 1 少一个顺串，那么磁带 1 最后一个顺出拷贝到磁带3最后就好。得到结果如下


磁带 3	$R_1\cdots R_{2,000,000};R_{4,000,001}\cdots R_{5,000,000}$
磁带 4	$R_{2,000,001}\cdots R_{4,000,000}$

所以磁带绕回开始位置，开始新的一轮合并。顺串 $R_{4,000,001}\cdots R_{5,000,000}$ 仅拷贝一下就好。如果我们有 800 万个记录，那么磁带 2 包含顺串 $R_{4,000,001}\cdots R_{8,000,000}$ 。


磁带 1	$R_1\cdots R_{4,000,000}$
磁带 2	$R_{4,000,001}\cdots R_{5,000,000}$

最后磁带绕后之后进行最后一轮合并，在磁带 3 上产生顺串 $R_1\cdots R_{5,000,000}$ ，排序完成。

平衡的合并可以扩展到任意 $T\geq 3$ 个磁带上。我们任选一个 $P,1\leq P<T$ 把 $T$ 个磁带分成两部分， $P$ 个磁带一部分，剩余 $T-P$ 个磁带另一部分。初始时把顺串尽可能均匀的分配到 $P$ 个磁带上，进行 $P$ 路合并，数据放到 $T-P$ 个磁带上，然后进行 $T-P$ 路合并，放回 $P$ 个磁带上，直到排序完成。 $P$ 的最佳选择是 $\lceil T/2\rceil$ 。（见习题 3 和 4）。

一开始觉得 $T$ 不能是3，因为会出现一路归并，这怎么可能。其实是可以的，一路归并就是依次把顺串交替的放到另外的两个磁带上。也就是习题 2 说的情况。

平衡的两路合并是 $T=4,P=2$ 这种特殊情况。我们用 $T=6,P=3$ 再来跑一下上面的例子。初始状态是


磁带 1	$R_1\cdots R_{1,000,000};R_{3,000,001}\cdots R_{4,000,000}$
磁带 2	$R_{1,000,001}\cdots R_{2,000,000};R_{4,000,001}\cdots R_{5,000,000}$
磁带 3	$R_{2,000,001}\cdots R_{3,000,000}$

第一个合并扫描之后，得到


磁带 4	$R_1\cdots R_{3,000,000}$
磁带 5	$R_{3,000,001}\cdots R_{5,000,000}$
磁带 6

第二次合并扫描之后就得到完全排序的顺串 $R_1\cdots R_{5,000,000}$ ，放在了磁带 1 上。对于这种情况，磁带 6 完全没有用上，所以 $T=5$ 和 $T=6$ 是完全一样的。只有 $S\geq 7$ 的时候，磁带 6 才能用上。

三路合并比两路合并的计算资源更多，但是相比起读、写绕回磁带所需要的时间，一般可以忽略不计。所以这里仅考虑磁带移动的数量即可。 $T=6$ 时只需要扫描两次，比 $T=4$ 时的三次要快三分之一。

平衡合并非常简单，但是不是发最佳的方式。比如最开始平衡的两路做法，进行了两次两路合并之后，磁带 3 和磁带 4 各包含一个顺串，而磁带 1 恰好要读取 $R_{4,000,001}\cdots R_{5,000,000}$ ，磁带 2 已经是空的了，与磁带 3 和磁带 4 做三路合并，输入到磁带 2 即可。平衡方案读取三次，共计读取 1500 万记录，而优化之后只需要读取 400 万 + 500 万 = 900 万的记录即可。

其实还可以做的更好，初始状态如下：


磁带 1	$R_1\cdots R_{1,000,000};R_{3,000,001}\cdots R_{4,000,000}$
磁带 2	$R_{1,000,001}\cdots R_{2,000,000};R_{4,000,001}\cdots R_{5,000,000}$
磁带 3	$R_{2,000,001}\cdots R_{3,000,000}$
磁带 4

进行一次三路合并放入磁带 4，然后磁带 3 和磁带 4 绕回开始的位置，然后三路合并输出到磁带 3 就完成了排序。共计读取了 300 万 + 500 万 = 800 万个记录。

当然，如果 $T=6$ ，五个顺串放在磁带 1 到磁带 5 上，然后做一次五路合并到磁带 6 就完成了排序。

这些简单的例子说明平衡合并并不是最好的，并且，对合并模式要进行深入的研究。

本章后面就是深入分析外排算法。5.4.1 小节会考虑内部排序产生初始的顺串，其中利用大多数数据存在次序能够得到超出内存长度的顺串；这个小节也讨论了合适多路合并的数据结构。

5.4.2 到 5.4.5 小节讨论最重要的合并模式。学习这些模式的时候，先不要去考虑实体的磁带的限制和待排序的实际数据，集中考虑逻辑磁带这个概念就好。5.4.6 小节会回过头研究实际情况对这些模式的影响。

5.4.7 和 5.4.8 小节讨论的不是以合并为基础的外排算法。最后 5.4.9 讨论了海量数据的问题以结束我们的讨论。

这本书写的时候大家都在用磁带，90 年代开始使用磁盘，所以很多磁带合并模式和现实关系有限了。

时至今日（2022年），一些服务器已经用上 NVME 了，读写的模式和以前差距更大。不过顺序读写依旧是最快的方式，所以这里很多思想还是很有用的。即使是内存，顺序读也是 cache 友好的。

许多模式非常优美，也是早年计算机领域的研究成果，很优雅，不必过早的扔到历史的垃圾堆中。理论和实际结合也是大有裨益的。

再者，思考这些问题本身也是一种享受。

习题

习题 1 我们可以忽略内排，直接外排，但是这样会慢很多，因为整个数据量要多好多次的全部读再全部写，以前面的例子为例子，一百万恰好是 $2^20$ ，平衡两路归并的就是要多 20 次，之前只需要 3 次，多 20 次，慢七倍。内存比外存快非常多，所以要利用好更快的存储。

习题 2 初始状态和 $T=4$ 一样


磁带 1	$R_1\cdots R_{1,000,000};R_{2,000,001}\cdots R_{3,000,000};R_{4,000,001}\cdots R_{5,000,000}$
磁带 2	$R_{1,000,001}\cdots R_{2,000,000};R_{3,000,001}\cdots R_{4,000,000}$
磁带 3

第一轮合并到磁带 3


磁带 3	$R_1\cdots R_{2,000,000};R_{2,000,001}\cdots R_{4,000,000};R_{4,000,001}\cdots R_{5,000,000}$

把磁带 3 的顺串交替拷贝回磁带 1 和磁带 2


磁带 1	$R_1\cdots R_{2,000,000};R_{4,000,001}\cdots R_{5,000,000}$
磁带 2	$R_{2,000,001}\cdots R_{4,000,000}$

再次合并到磁带3


磁带 3	$R_1\cdots R_{4,000,000};R_{4,000,001}\cdots R_{5,000,000}$

再拷贝回磁带 1 和磁带 2


磁带 1	$R_1\cdots R_{4,000,000}$
磁带 2	$R_{4,000,001}\cdots R_{5,000,000}$

最后合并一次到磁带 3 完成排序。总共需要访问数据五次，比 $T=4$ 的时候多两次。

其实一路合并就是要交替的把数据拷贝一次，所以相比之前的合并算法，除了初始状态，每次合并之前都需要完整的拷贝一次。所以 $T=4$ 的平衡两路合并需要 $n$ 次数据拷贝的话，那么 $T=3$ 需要 $2n-1$ 次。

习题 3 可以用归纳法证明。两个证明的递归部分是一样的。假设 $k$ 时成立，考虑 $k+1$ 的情况， $S$ 多了 $P(T-P)$ 倍，从 $P$ 个磁带进行 $P$ 路合并到 $T-P$ 个磁带， $S$ 少 $P$ 倍，从 $T-P$ 个磁带到 $P$ 个磁带，又少 $T-P$ 倍，所以比原来多 2 次。 $2k+2$ 或 $2k+2+1$ ，所以递归成立。

前者最小 $k$ 的值是 1，也就是 $P<S\leq P(T-P)$ ，就像上面递归过程一样，两次完成排序，所以 $k=1$ 时成立。后者最小值是 0，即 $0<S\leq P$ ，直接一次就能排序完成，所以 $k=0$ 时成立。

$T=2P$ ， $P^kP^{k-1}<S\leq P^kP^k$ ，显然 $2k=\lceil \log_P S \rceil$ 。对于任意 $P, T$ ，稍稍改写下右边 $\sqrt{P(T-P)}^{2k}$ ，得到 $\lceil \log_{\sqrt{P(T-P)}} S \rceil$ 。

习题 4 从函数角度来看 $f=P(T-P)$ ，很容易得到 $P=T/2$ 时取得最大值。