定义

它是设计用来处理数量很大的输入数据。当输入数据无法全部读入主存，可使用外部排序对数据进行排序。对于外部排序而言，排序的时间主要花费在对数据的读取和写入（例如对磁盘的读写），而在内存中的排序时间就显得无足轻重了。

多路合并算法

举例说明，假设需要排序的int数有12个，内存一次只能装下4个。

接下来把12个数据分成3份，然后排序成有序子串。

用3个指针读取3个有序子串，每次读取一个，将3个数中最小的数写到磁盘中，对应最小数所在的指针向后移动一位，再次读取一个数，重复上面步骤，直至3个指针都读取完毕，则所有数据按顺序写入到磁盘中。

以上例子可称为N路合并算法，N=3；

替换选择算法

替换选择算法考虑的是子串的分割。上面的多路合并算法中，采取的子串分割算法是比较简单的一种，即读入内存允许的最大数目作为一个子串，每个子串的数目也一致（除了最后一个子串可能不满足）。如果在对子串进行分割时，能够使得子串的数目尽量少，那么排序时对磁盘的读写次数也会下降，排序时间也会下降。想使子串的数目尽量少，就要使得每个有序子串（磁盘）中的数字尽量多，替换选择算法提供如下的实现方案。

我们可以从12个数据读取4个存到内存中，用这4个数构建最小堆，然后将堆顶的最小数放进子串p1里；

之后再从在从剩余的数据中读取一个数放到内存中，对这个数进行判断：如果这个数大于上一步骤中放入子串p1中的数，那么可以将这个数加入堆中，进行堆调整；如果这个数小于上一步骤中放入磁盘的数，那么这个数不加入堆中（但仍然在内存中），对剩下的数进行堆调整；然后再从将堆顶的最小数放进子串p1里，详细步骤如下。

读入3（3比2大，加入堆）：

读入24（24比3大，加入堆）：

读入8（8比24小，不加入堆，暂放一边，但仍在内存中）：

读入87（87比70大，加入堆）：

读入17（17比81小，不加入堆，暂放一边，但仍在内存中）：

读入46（46比86小，不加入堆，暂放一边，但仍在内存中）：

读入30（30比87小，不加入堆，暂放一边，但仍在内存中）：

此时堆中已经没有可以加入到p1子串的数字了，至此，p1顺序子串构建完毕；

然后，进行第二个子串p2的构建，对内存中的4个数重新构建最小堆，重复上面的步骤。

最后构建出的p2顺序子串如下：

相比多路合并算法中得到的3个顺序子串，替换选择算法只得到2个顺序子串；

后面的步骤是一样的，较少的子串意味着较少的磁盘IO，当然内存排序时间也较少。值得一提的是，替换选择算法中采取堆排序算法的思想（优先队列），这样使得每读入一个新的数字之后，不需要重新进行排序，只需要对堆结构进行调整即可，即堆的一次deleteMin和一次insert操作；

源文档链接：【漫画】什么是外部排序？_p1