多路归并排序

将原文件分解成多个能够一次性装入内存的部分，分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行多路归并排序。

步骤

1. 按照内存大小，将大文件分成若干长度为 $l$ 的子文件（$l$ 应小于内存的可使用容量） 
2. 然后将各个子文件依次读入内存，使用适当的内部排序算法对其进行排序(排好序的子文件统称为“归并段”或者“顺段”） 
3. 将排好序的归并段重新写入外存，为下一个子文件排序腾出内存空间 
4. 对得到的顺段进行合并，直至得到整个有序的文件为止

如上图所示有 10 个初始归并段到一个有序文件，共进行了 4 次归并，每次都由 2 个归并段得到 $\lceil m/2\rceil$ 个归并段，这种归并方式被称为 2-路平衡归并

效率分析

• 影响整体排序效率的因素主要取决于IO次数，即访问外存的次数越多，算法花费的时间就越多，效率就越低
• 对于同一个文件来说，对其进行外部排序时访问外存的次数同归并的次数成正比，即归并操作的次数越多，IO的次数就越多
• 提高效率的方法：
  1. 增加 k-路平衡归并中的 $k$ 值
  2. 尽量减少初始归并段的数量 $m$，即增加每个归并段的容量
• 对于具有 m 个初始归并段进行 k-路平衡归并时，归并的次数为：$s=\lfloor logkm\rfloor$（其中 s 表示归并次数，注意是向下取整）

优化

最佳归并树

置换选择排序

败者树