一般讨论的排序都是内部排序，所谓外部和内部，是针对排序时的条件而言的，内部指所有的数据都可以直接拿到，而外部就是每次只能拿到一部分数据，最典型的现实场景
- 对数组进行排序，整个数组当然都是在内存里的，可以直接拿到
- 而对磁盘数据（比如文件）进行排序，要先把数据读进内存，而且限于内存的大小，内存中在某一时刻只能有一部分数据
外部排序的限制在于从磁盘读数据是一件很麻烦的事情，因为在磁盘上的数据存储并不是和在内存中那样是连续的，有个地址就可以直接访问，而是分散的，而且每次找一个数据都得寻道，旋转，再数据传输，排序的结果还得再写回磁盘，实际磁盘I/O的时间会远超在内存上操作的时间，所以要尽可能减少对磁盘的访问，I/O次数也成为外部排序时主要考虑的代价
这时候可以选什么排序算法来进行外部排序呢，很明显，选择排序，冒泡排序，这种每一趟都得把数据基本过一遍的算法是不行的，实际上可以想到，归并排序是个不错的选择
例如，一个有2000个记录的文件，每个磁盘块可以容纳125个记录，首先通过8次内部排序得到8个初始归并段R1到R8，每个段有250个记录，然后对该文件做两两归并，直至得到一个有序的文件
把内存分出三个缓冲区，两个输入一个输出，从R1和R2分别读一个磁盘块到输入缓冲区，归并到输出缓冲区，钥匙其中一个缓冲区空了就再读一个，然后把输出写到磁盘，再归并R3和R4，R5和R6，R7和R8，分别得到R1’-R4’
R1--R2 R3--R4 R5--R6 R7--R8
｜ ｜ ｜ ｜
R1' ------- R2' R3' ------- R4'
| |
R1'' ------------------ R2''
|
R这样的话，一躺归并要读16个磁盘块，写16个磁盘块，内部排序也要读16次，写16次，总共的I/O次数：
$$
32\times 3 + 32=128
$$
如果改成四路归并，就只需要2趟归并：
R1--R2--R3--R4 R5--R6--R7--R8
| |
R1' --------------- R2'
|
R这样外部排序的I/O次数就少了，但这样需要内存提供更多的缓冲区
败者树
增加归并排序的路数k固然可以减少I/O次数，但是内部归并的时间却增加了，因为在k个元素中选一个最小的需要做k-1次比较，每趟归并n个元素，要比较$(n-1)(k-1)$次，r个初始归并段，S趟归并总共需要的比较次数为：
$$
S(n-1)(k-1)=\log_k r(n-1)(k-1)=\frac{\log r}{\log k}(n-1)(k-1)
$$
可以看到随着k的增大，内部归并的时间也变多了，这时候就不能用普通的内部归并算法了
败者树主要用于选出k个元素里最小的那个，比如有8个元素，先两两比较，选出4强，再半决赛，在决赛，最后胜利的一定是冠军，但是只比了3次
a
|
a ------------- e
| |
a ----- c e ----- g
| | | |
a---b c---d e---f g---h显然败者树是一颗完全二叉树，k路归并的话，从k个数据里选最小的，比较的次数为$\log k$，总的比较次数为
$$
S(n-1)\log k=(\log_k r)(n-1)\log k=(n-1)\log r
$$
这样内部归并比较的次数就与k无关了
但即使是这样，k也不是越大越好，k增大时，内存要提供更多个数的缓冲区，每个缓冲区的容量就会变小，内外存交换的次数会增加，因此当k过大时，归并趟数会减少，但外存I/O次数还是会增加
置换-选择排序
还有什么优化的方向呢，减少初始归并段的个数$r$也开始减少归并趟数S，内部排序在生成初始归并段的时候，依赖于内存工作区，只能生成相当于内存工作区大小的初始归并段，有什么操作可以跳出这个限制呢
基本思路是这样的
- 一个工作区，大小为w，先从文件读w个记录进去
- 从工作区里选一个最小的，输出并把值记录下来
- 往工作区里补一个记录，再找一个最小的但是比已经输出的值要大的，输出
- 重复，直到找不到比已经输出的值要大的
- 结束，一个初始归并段生成了
其中“从工作区里的w个记录里找一个最小的”的操作是基于败者树的
最佳归并树
置换-选择排序后，产生了一系列不等长的初始归并段，那么如何安排归并顺序呢，显然不同的顺序开销是不同的
比如，有9个初始归并段，长度为9，30，12，18，3，17，2，6，24
[9]-[30]-[12] [18]-[3]-[17] [2]-[6]-[24]
| | |
[51] ---------- [38] ---------- [32]
|
[121]归并树的带权路径长度（WPL）为归并过程中的总读记录数，在上面的归并树中，WPL=242
实际上，可以用Huffman树的思想来优化归并树，将比较小的归并段先归并
[2]-[3]-[6]
|
[9]-[11]-[12] [17]-[18]-[24]
| |
[30]-----[32]------------[59]
|
[121]这样的话，WPL只有223（把除了根节点的每个节点的值都加起来）
其实上图中的Huffman树是一颗严格的三叉树，即节点的度要么是0要么是3，但实际场景中这种刚刚好的场景是很少的，比如缺一个30，这时候构造Huffman时最后一次归并将是2路归并，WPL为193，但这并不是最优的
正确的做法应该是：补上1个值为0的节点
[0]-[2]-[3]
|
[5]-[6]-[9] [12]-[17]-[18]
| |
[20]--------[24]---------[47]
|
[91]那么如何确定应该补几个0节点呢？
- 设度为0的节点有$n_0$个，度为k的节点有$n_k$个，如果是严格k叉树，有$n_0=(k-1)n_k+1$
- 也就是$n_k=(n_0-1)/(k-1)$
- 如果$k-1|n_0-1$，说明刚好
- 如果$n_0-1\equiv u \mod k-1$，说明多出来$u$个，补上$k-1-u$个就好了
注意，初始节点全是度为0的节点
比如，8个初始节点，3路归并，$8-1\equiv1\mod 3-1$，多1个，补1个
总结
外部排序相较于内部排序，很重要的一点是考虑了实际环境的限制，而且外部排序的过程中也涉及到了内部排序
在外部排序的优化过程中，除去优化的方法，优化的思路更值得关注