引入

内存空间紧张

在之前的排序中，我们排序数据都是将数据直接加载到内存中然后再进行排序，但是如果要加载的数据很大，例如有 400 G 的数据，要想一下子全部加入进内存中，明显是不现实的。

我们能做的只是把一部分的数据先加载中内存中处理，然后再处理另一部分的内容。然后再将各个部分 merge 成一个完整的有序段。这个思路利用的归并排序的思路。

读写效率紧张

我们都知道 IO 速度是远远内存运算的速度的。也就是说，当我们尝试将文件数据读入内存的时候，会花费比排序长的多的时间。所以，我们应当尽可能的减少 IO 的次数。从而从整体上提高排序的效率。

如果我用常规的二路归并（也就是每次只合并 2 段），那么势必会造成 IO 次数太多。如果我们将二路归并的过程看成一颗树，如下图：

当我们尝试将二路归并拓展成四路归并：

我们会发现树的高度降低了。于是 IO 的次数就降低了。于是可以通过增加路数来减少 IO 次数。多路平衡归并

因为，我们每次都要从内存中读入这些归并段（r1,r2,r3,...r8）然后将合并后的结果，例如 r1',r2',... 在重新写到内存中。树的高度每增加 1，就意味着，就要多一个读写的流程。

同时，如果我能够减少初始归并段 r 的数量，那么也能有效的减小 IO 次数，从而提高效率。置换-选择排序

二路归并流程

如上图，在内存中，我们只有一个输出缓冲区和输入缓冲区来进行归并的操作。当我们想要读入序列的时候，就把磁盘块读入两个输入缓冲区，在这两个缓冲区中做 merge 操作，正如我们在归并排序中所做的那样。然后将归并的内容移动到输出缓冲区中，最后写到磁盘中即可。