外部排序
由于数据元素太多，无法一次全部读入内存进行内部排序，这是就要通过外部排序来解决
1.外排原理
目的：通过内存的读写操作(每次读写操作都是成块的进行，比如每次1KB)，将存放于磁盘中的大量数据变得有序。
(拿二路归并举例)
如图，对于在磁盘中分块存放的数据，每块存入三个元素，共16块
在内存中建立三个缓冲区输出缓冲区、输入缓冲区1以及输入缓冲区2
1.1构造初始归并段
首先，依次地读入前两块数据，分别存入内存中的 缓冲区1、缓冲区2
将输入缓冲区1以及输入缓冲区2中存放的数据经过 内存中的二路归并排序(内排)后，将生成的有序的块经 输出缓冲区 写入磁盘 得到一个有序的归并段
同样的，对剩余块进行同样的操作可以得到
1.2以归并段为单位进行归并
分别选取归并段1和2中较小的一块，依次读入至缓冲区1,2
内排之后，写入内存，注意，输入缓冲区1(或2)空缺后要立即在归并段1(或2)中读入新的块到其中进行归并排序
（以保证输出缓冲区始终输出归并段中较小的元素）
最终，完成所有归并段的第一趟归并之后，会有
之后，4块成一个归并段，两两归并
……
最终。经过3趟归并，整体会变得有序！
2.优化思路
2.1时间开销分析
在整个排序过程中，时间开销分析如下
可以看到，
外部排序时间开销=读写外存的时间+内部排序所需时间+内部归并所需时间
而读写外存时间是关键的时间开销，因此优化应该针对怎么减少读写外存的次数展开
而文件总块数无法优化，只能针对归并的趟数优化
为此，我们需要采用多路归并来解决
2.3结论
2.4 优化思路一：采用多路归并
对上面的例子，如果采用四路归并
只需96次读写即可！！
2.5 优化思路二：减少初始归并段数量r
败者树
归并段数增加之后，内存中缓冲区数目增加，从中对比得出最小关键字的对比次数也会随之增多……
1.算法思想
构造 如图所示的树结构，叶节点对应（脑补）各归并段（假设共有8个归并段），分支结点记录败者来自哪个归并段，最后根节点记录冠军来自哪个归并段，并且将冠军输出，为这8个归并段中的最小值。
下轮选择冠军记录的那个归并段（归并段3）中的元素6，代替1的位置，如图，并依次向上的与各败者结点对比，胜则往上，败则留下，最终输出冠军
接下来，循环这个过程
2.效率分析
对于k路归并，第一次构造败者树需要对比关键字k-1次 有了败者树，选出最小元素，只需对比关键字次$\left \lceil \log_2k \right \rceil$
置换选择排序
⽤于内部排序的内存⼯作区WA可容纳l个记录，则每个初始归并段也只能包含l个记录，若⽂件共有n个记录，则初始归并段的数量r=n/l,这是之前的做法
1.算法思想
设初始待排文件为F，初始归并段输出文件为FO，内存工作区为WA,FO和WA的初始状态为空，WA可容纳w个记录。置换选择算法的步骤如下： 1）从F输入个记录到工作区WA。 2）从WA中选出其中关键字取最小值的记录，记为 MINIMAX记录3）将MINIMAX记录输出到FO中去。 4）若F不空，则从F输入下一个记录到WA中。 5）从w中所有关MINIMAX键字比记录的关键字大的记录中选出最小关键字记录，作为新的MINIMAX记录。 6）重复3）~5），直至在A中选不 MININ出新的记录为止，由此得到一个初始归并段，输出一个归并段的结束标志到FO中去。 7）重复2）~6），直至WA为空。由此得到全部初始归并段。
最佳归并树
利用置换选择排序构造初始归并段，归并段长短不一
对于一个归并树，如图数字表示该归并段占多少个磁盘块。
每个初始归并段看作⼀个叶⼦结点，归并段的⻓度作为结点权值，则 上⾯👆这棵归并树的带权路径⻓度 WPL = 2*1 + (5+1+6+2) * 3 = 44
重要结论：归并过程中的磁盘I/O次数 = 归并树的WPL * 2 16 = 读磁盘的次数 = 写磁盘的次数
因此
我们可以构造出一棵带权路径最小的归并树——哈夫曼树！
注意：
对于k叉归并，若初始归并段的数量⽆法构成严格的 k 叉归并树， 则需要补充⼏个⻓度为 0 的“虚段”，再进⾏ k 叉哈夫曼树的构造
①若（初始归并段数量 -1）% （k-1）= 0，说明刚好可以构成严格k叉树，此时不需要添加虚段
②若（初始归并段数量 -1）% （k-1）= u ≠ 0，则需要补充 (k-1) - u 个虚段