置换——选择排序

土办法构造初始归并段

同时最多放两个到输入缓冲区，只能读入两块的内容，然后把这些记录在内存排序之后，在输出写回外存，这样就得到了一个初始归并段。

由于内部排序的内存工作区只能容纳6个记录（例子）。

可以用一片更大的内存区域来进行内部排序（如：可容纳18个记录）

用于内部排序的内存工作区WA可容纳l个记录，这就意味着构造的初始归并段也只能包含l个记录，若文件共有n个记录的话，则初始归并段数量r=n/l

注：假设用于内部排序的内存工作区只能容纳3个记录

刚开始会在待排序的文件当中读入3个记录

我们要构造递增的归并段

检查内存工作区中的记录，把关键字最小的记录”置换“出去，并且用一个变量MINIMAX把刚才输出的关键字的值给记下来

现在内存工作区中有一个空位，会在FI读入下一个记录

再把最小的置换出去，并且用MINIMAX记录。

读着读着，

此时，内存工作区当中最小的一个记录是10，但是通过MINIMAX这个变量我们知道，之前输出到归并段1的记录到13了，所以10这个记录我们不能放到归并段1的末尾。

除了10 就是到14比13大，所以我们可以把14放到归并段1的末尾

紧接着读入下一个。。

读到2的时候最小的比MINIMAX小，所以不能放到归并段1的末尾

所以把30放出到归并段1的末尾。

在一直放。。

如果在某一个时刻WA内的关键字都比MINIMAX更小，则该归并段在此截至。

接下来构造归并段2

。。。

接下来构造归并段3

。。。

这些初始归并段的长度可以超越内存工作区的大小的限制

读写磁盘是以磁盘块为单位的。