外部排序的基本思想就是归并排序。
1 二路平衡归并
- 按照内存大小，将大文件分成若干长度为 l 的子文件（l 应小于内存的可使用容量），然后将各个子文件依次读入内存，使用适当的内部排序算法对其进行排序（排好序的子文件统称为“归并段”或者“顺段”），将排好序的归并段重新写入外存，为下一个子文件排序腾出内存空间；
- 对得到的顺段进行合并，直至得到整个有序的文件为止。
注意：在实际归并的过程中，由于内存容量的限制不能满足同时将 2 个归并段全部完整的读入内存进行归并，只能不断地取 2 个归并段中的每一小部分进行归并，通过不断地读数据和向外存写数据，直至 2 个归并段完成归并变为 1 个大的有序文件。
想要达到减少归并次数从而提高算法效率的目的，可以从两个角度实现：
- 增加 k-路平衡归并中的 k 值；
- 尽量减少初始归并段的数量 m，即增加每个归并段的容量；
2 多路平衡归并算法
为了避免在增加 k 值的过程中影响内部归并的效率，在进行 k-路归并时可以使用“败者树”来实现，该方法在增加 k 值时不会影响其内部归并的效率。
败者树实现内部归并
胜者树和败者树的区别就是：胜者树中的非终端结点中存储的是胜利（左右孩子相比较，谁最小即为胜者）的一方；而败者树中的非终端结点存储的是失败的一方。而在比较过程中，都是拿胜者去比较。
- 首先将k个归并段中的首元素关键字依次存入b[0]–b[k-1]的叶子结点空间里，然后调用CreateLoserTree创建败者树，创建完毕之后最小的关键字下标（即所在归并段的序号）便被存入ls[0]中。然后不断循环：
- 把ls[0]所存最小关键字来自于哪个归并段的序号得到为q，将该归并段的首元素输出到有序归并段里，然后把下一个元素关键字放入上一个元素本来所 在的叶子结点b[q]中，调用Adjust顺着b[q]这个叶子结点往上调整败者树直到新的最小的关键字被选出来，其下标同样存在ls[0]中。循环这个 操作过程直至所有元素被写到有序归并段里。
3 置换选择排序算法
减少初始归并段的个数也能提高外部排序效率。
假设内存工作区最多可容纳 6 个记录
- 首先从初始文件中输入 6 个记录到内存工作区中；
- 从内存工作区中选出关键字最小的记录，将其记为 MINIMAX 记录；
- 然后将 MINIMAX 记录输出到归并段文件中；
- 此时内存工作区中还剩余 5 个记录，若初始文件不为空，则从初始文件中输入下一个记录到内存工作区中；
- 从内存工作区中的所有比 MINIMAX 值大的记录中选出值最小的关键字的记录，作为新的 MINIMAX 记录；
- 重复过程 3—5，直至在内存工作区中选不出新的 MINIMAX 记录为止，由此就得到了一个初始归并段；
- 重复 2—6，直至内存工作为空，由此就可以得到全部的初始归并段。
通过置换选择排序算法得到的初始归并段，其长度并不会受内存容量的限制，且通过证明得知使用该方法所获得的归并段的平均长度为内存工作区大小的两倍。