外部排序

http://data.biancheng.net/view/77.html

---

多路归并排序：

对于外部排序算法来说，影响整体排序效率的因素主要取决于读写外存的次数，即访问外存的次数越多，算法花费的时间就越多，效率就越低。

对于同一个文件来说，对其进行外部排序时访问外存的次数同归并的次数成正比，即归并操作的次数越多，访问外存的次数就越多（每次归并都要加载硬盘上的待归并文件到内存）。

• 最后一轮归并的时候内存不够怎么办？

在实际归并的过程中，由于内存容量的限制不能满足同时将 2 个归并段全部完整的读入内存进行归并，只能不断地取 2 个归并段中的每一小部分进行归并，通过不断地读数据和向外存写数据，直至 2 个归并段完成归并变为 1 个大的有序文件。

• 有关段的预处理如何提升算法效率？

对比2-路还有5-路归并排序可以看出，对于 k-路平衡归并中，增加 k 可以减少归并的次数，从而减少外存读写的次数，最终达到提高算法效率的目的。除此之外，一般情况下对于具有 m 个初始归并段进行 k-路平衡归并时，归并的次数为：$s=⌊log_k⁡m ⌋$（其中 s 表示归并次数）

-方法也就以下两个：
（1）增加 k-路平衡归并中的 k 值；（多路平衡归并算法）
（2）减少初始段的数量m / 增加每个归并段的容量（段太大的话内存可能不够）；（置换-选择排序算法）