7.7.4 置换选择排序（生成初始归并段）

7.7.3讨论了如何使用m路归并来减少磁盘访问次数。从第7.7.2的讨论可知，减少初始归并段个数r也可以减少归并趟数S。若总的记录个数为n,每个归并段的长度为L,则归并段的个数m=[n/L]。如果采用前面介绍的内部排序方法，将得到长度相同的初始归并段。因此，必须探索新的算法俩生成初始归并段，这就是本节介绍的置换-选择算法。

设初始待排文件FI,初始归并段文件为FO,内存工作区为WA,内存工作区可容纳W个记录。置换-选择算法的步骤如下：

1）从待排文件FI输入W个记录到工作区WA.

2）从内存工作区WA中选出其中关键字最小的记录，记为MINIMAX.(以后再选出关键字比它大的记录纳入本归并段，比它小的归入下一归并段)

3）将MINIMAX记录输出到FO中去。

4）若FI未读完，则从FI输入下一个记录到WA中。

5）从WA中所有关键字比MINIMAX记录的关键字大的记录中选出最小的关键字记录，作为新的MINIMAX。

6）重复3）~5）直到在WA中选不出新的MINMAX记录为止，由此得到一个初始归并段，输出一个归并段的结束标志到FO中去。

7）重复2）~6）直到WA为空，由此得到全部初始归并段。