1.基本概念

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

说明：本节是2012年统考数据结构考研大纲的新增内容。

说明：外排序的对象有记录、页等（注意区别于内部排序的“关键字”），本节中一律称之为记录。

2.流程解析

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

假设要对外存中一组大规模无序记录进行归并排序，则可以按照如下步骤进行。

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

2）将这m个有序记录段每k段分为一组，得到m/k组记录段。取其中一组，如图8-15所示（假设k等于5），每行一段，将每段段首的记录读入内存，如图中灰色处所示。

图8-15 5个有序记录段为一组

3）用某种算法从读入内存的这组记录中选出最小的，如图8-16所示。

图8-16 选出最小值1(www.daowen.com)

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

图8-17 将最小值1写回外存中，此时得到含有一个记录的有序段

5）重复以上过程，如图8-18所示。

图8-18 将最小值2写回外存，此时得到含有两个记录的有续段

6）当此组记录全部导出之后，就会在外存中得到一个较长的有序记录段。以此方法将剩下的所有组记录段都归并成较长的记录段，就得到了m/k个较长有序记录段。将这m/k个较长有序记录段按照同样的方法分组、归并，并重复此过程，最终就可以完成对这n个记录的排序。可以看到，整个过程中只用了k个内存空间，达到了用较小的内存空间完成较大规模记录排序的目的。

说明：上边算法称为k路归并算法，如果k等于2，就是我们之前熟悉的二路归并排序算法的外存版。

3.重要子算法

1）置换-选择排序。上边步骤1）中的m个有序记录段称为初始归并段。如果被划分的每个小记录段规模不够小，仍然无法完全读入内存，则无法用内排序得到初始归并段，因此需要一种适用于初始归并段规模的、高效的且不受内存空间限制的排序算法，即置换-选择排序。

2）最佳归并树。将当前的m组（每组含有k个有序记录段）记录归并为m个有序记录段的过程称为一趟归并，可见每个记录在每趟归并中需要两次I/O操作（读写操作各一次）。读写操作是非常耗时的，可见减少归并次数可以提高效率。为了使得归并次数最少，需用到最佳归并树。

3）败者树。归并排序算法中有一个多次出现的步骤是从当前k个值中用某种算法选出最值，可见提高选最值的效率也是整个归并排序算法效率提高的关键。这就需要用到败者树。