什么是外部排序

我们常用的排序算法有冒泡排序、插入排序、快排等等，这些排序使用的数据统一都在内存中，故称为内部排序。

那与之对应，外存中的数据进行排序称为外部排序，这就是外部排序的定义。

需要注意的是在外存中的数据是不可能在外存中就排好序的，还是需要将数据调入内存中，使用内部排序（通常采用归并排序）进行排序。

外部排序的过程

基本概念

数据在外存中会被划分为一个一个的块，数据就在这些块中，计算机的I/O操作是以块为单位的。

内存中存在输入缓冲区和输出缓冲区，输入缓冲区有k个就可以进行k路归并排序，并将经归并排序后有序的数据输出到输出缓冲区中，当输出缓冲区中的数据有一个块大小时，就将其输出到外存（这也对应了输入输出以块为单位）。

根据内存缓冲区的大小，将外存上的文件分成若干长度为m的子文件，依次读入内存并利用内部排序算法对他们进行排序，排序后得到的有序子文件重新写回外存，称这些有序子文件为归并段或有序串。

具体过程

假设：内存中存在两个输入缓冲区，一个输出缓冲区。

外存上有2000个记录，一个块可以存放125个记录，显然外存上有16个块。

首先，两个输入缓冲区分别读入一个块，对其进行二路归并排序，得到在外存上的两个块大小的有序段，这样外存上就可以得到初始化的8个归并段。

接着，将8个归并段依次进行二路归并排序，又可以得到4个更大的归并段，以此类推，直到整个文件全部有序为止。

使用上述过程，就可以将整个外存中的数据排好序。

分析

因为外部排序时间主要是在I/O操作上，所以想要减少外部排序的时间就需要减少I/O操作。

我们分析一下上述过程，初始化的 8 个归并段要经过二路归并排序全部排好序显然需要 3 趟，而一趟就分别需要 16 次读操作和写操作，再加上得到初始归并段的 1 趟操作，故总共需要次 32×2+32=96 次I/O操作。

在内存输入缓冲区大小一定的情况下，初始归并段只能为 8 个，若增加为四路归并排序，那么就只需要 2 趟，那么总共需要 32×2+32=96 次I/O操作则可。

显然，k路归并，k越大进行的I/O操作在一定范围内就越少（至少得一趟），但k是越多越好吗？答案是否定的。k越大，内部排序需要的时间就越多，当k大到一定值时，内部排序多出的时间就会抵消掉减少的I/O操作时间！

除了增加 k 这种方法，还有减少初始段个数的方案，接着往下看吧。

外部排序的优化

上面形成的初始归并段大小是收到内存输入缓冲区大小的限制的，初始的归并段出最后一个其余的都为输入缓冲区大小。

但是要减少初始归并段个数，必须得增大每个归并段的数据呀，所以需要使用一种新的算法来确定初始归并段。

待排序文件为FI，初始归并段输出文件为FO，内存工作区为WA，WA大小为w，FO和WA初始状态为空。

注意：WA和内存输入缓冲区位于不同的地方，是两个不同的东西。

算法步骤：

  1. 将FI中的w个记录输入到WA中；

  2. 从WA中选取最小值并记为MINMAX；

  3. 将MINMAX输出到FO中；

  4. 若FI不为空，则从FI中输入下一个记录到WA中；

  5. 从WA中大于等于MINMAX的记录中选取最小的一个作为新的MINMAX；

  6. 重复3~5，直到WA中无法选出一个新的MINMAX为止，得到一个初始归并段，输出一个归并段结束的标志到FO中；

  7. 重复2~6，直到WA为空，得到所有初始归并段。

这样做的话，虽然WA大小是w，但选取的初始归并段大小却不止w，甚至远超w，这样一来，初始归并段的个数明显减少，从而达到减少I/O操作的目的了。

在选取MINMAX时，采用的是败者树进行的。

败者树

败者树可以视为一颗完全二叉树。

若采用 k 路归并，则该败者树的叶子结点存放 k 个初始归并段中需要比较的元素，分支结点中存放失败结点。举个例子：需要得到最小值（成功），那么将每个叶子结点的值进行比较，大的值（失败）保留到分支结点中，同一层的结点又再次比较，其父结点又保存大的值，依次类推，最后可以得到最小的值，也就是成功节点。

这样比较一次，可以得到一颗对应的败者树，下次比较就可以很快得出最小值了。分支结点中存放元素的归并段序号更好，因为这样可以直接锁定从哪一个归并段中得到的最小值，直接可以从该归并段中拿出下一个元素到对应叶子结点上继续比较了。

采用败者树，进行的I/O操作就可 k 无关了，但是也不是 k 越大越好，因为在可使用的内存大小不变的情况下，k 越大则输入缓冲区的个数就越多，输入缓冲区大小就越小，若输入缓冲区大小都小于块大小了，则一个块就会触发多次I/O操作了，从而导致时间变长。

其实败者树在体育赛事中十分常见，乒乓球、羽毛球等个人赛一般都是采用的败者树进行的。

最佳归并树

得到了尽可能大的初始归并段了，需要将它们联系起来，采用的方法就是最佳归并树。

采用 k 路归并，则需要 k 个归并段进行操作，那么可以形成一颗 k 叉树撒，初始归并段作为叶子结点，除根结点外的分支结点作为形成的有序子文件，根结点作为整体有序文件。

这里利用 哈夫曼树 这种数据结构，每个结点中的数值表示归并段大小，要让整体的I/O操作更少，等价于形成树的WPL最小，故就需要构造一颗哈夫曼树。

但是这里的哈夫曼树和之前的有点不同，这里需要引入 虚段（段中没有数据的归并段），一颗 k 叉的哈夫曼树，怎样判断需不需要引入虚段呢？

设：有 n 个初始归并段，采用 k 路归并。

(n - 1) % (k - 1) = u，判断u是否为0，若为0，则表示不需要引入虚段，否则表示需要引入虚段。

引入虚段的个数为：k - u - 1 。