采用置换-选择排序算法构造初始归并段的过程：根据缓冲区大小，由外存读入记录，当记录充满缓冲区后，选择最小的（假设升序排序）写回外存，其空缺位置由下一个读入记录来取代，输出的记录成为当前初始归并段的一部分。如果新输入的记录不能成为当前生成的归并段的一部分，即它比生成的当前归并段中最大的记录要小（如例8-1中的关键字11比15要小，则暂时不能出现在当前归并段中），则它将成为生成其他初始归并段的选择。反复进行上述操作，直到缓冲区中的所有记录都比当前初始归并段最大的记录小时（如表8-1中步数9中的所有关键字都比83小，则以83为结尾的归并段生成完毕），就生成了一个初始归并段。用同样的方法继续生成下一个初始归并段，直到全部记录都处理完毕为止，这就是置换-选择排序法。

下面通过例题来具体说明一下。

【例8-1】 设一组输入记录为：

15，19，04，83，12，27，11，25，16，34，26，07，10，90，06…

假设内存缓冲区可容纳4个记录，生成初始归并段。表8-1给出了生成初始归并段过程中各步的缓冲区内容和输出结果。

表8-1 初始归并段生成过程(www.daowen.com)

注：表中下划线数字即为生成下一归并段的候选数字。

说明：上一节提到的限制排序算法的内存空间就是指本题中的缓冲区，在其他场合还可能有其他叫法，这里考生要注意。

由例8-1可知，通过置换-选择排序算法得到的m个初始归并段长度可能是不同的。不同的归并策略可能导致归并次数的不同，即意味着需要的I/O操作次数不同，因此需要找出一种归并次数最少的归并策略来减少I/O操作次数，以提高排序效率。这就引出下一个知识点——最佳归并树。