整理自《数据结构高分笔记》

1、概念和流程

基本概念
所谓外部排序，即对外存中的记录进行排序（相对于内部排序而言），有了内部排序算法，为什么还需要外部排序？因为外存中记录规模太大，内存放不下。外部排序可以概括为一句话：将内存作为工作空间回来辅助外存数据的排序。

流程解析
外部排序最常用的算法是归并排序，是因为它不需要将全部的记录都读入内存就可以完成排序，因此，可以解决由于内存空间不足导致的无法对大规模记录进行排序的问题。

1）将这组记录假设为n个，分为m个规模较小的记录段（记录段的长度不一定相等），并对这些小记录段进行排序，一般情况下这些记录段都足够小，可以整段读入内存并选择合适的排序算法对其排序。

2）将m个有序记录每k个分为一组，得到ceil（m／k）组记录段，取其中一组，假设k=5，如下图所示，每行一段，将每段的段首的记录读入内存，如图中灰色的所示：

3）用某种方法从读入内存的这组记录中选出最小的，比如下面我们选择1.

4）将上一步选出的最小值写回外存，并将其所在记录段的次小值读入内存补上空位置，如图：

5）重复以上过程

6）当此组记录全部导出之后，就会在外存中得到一个较长的有序记录段。以此方法将剩下的所有组记录段都归并成为较长的记录段，就得到了ceil(m/k)个较长的有序记录段，然后按照上面同样的方法分组、归并、排序，并重复此过程，就可以完成对这n个记录的排序。