前情提要

image.png

土办法构造初始归并段

土方法构建初始归并段的包含的记录限制于缓冲区的容量之和。当然可以用更大的缓冲区。
image.png
image.png

置换-选择排序构造初始归并段

可以构造比内存工作区更大的初始归并段。

实现过程

有如下初始待排序文件（储存在硬盘中）和一个内存工作区（容量为3个记录）进行置换-选择排序构建递增的归并段。
image.png
最开始从待排序文件中读入三个记录（填满内存工作区，先将好几个数据读入好内存的缓冲区再由缓冲区读入内存工作区）。
image.png
把最小的记录”置换除去“。（输出到硬盘里面，此处应该先将记录保存在输出缓冲区中，之后再有输出缓冲区进行输出）并且记录此时输出的是多少。
image.png
从待排序工作区中读入下一个记录。重复上面操作。如果比记录的输出的元素大，则执行”置换“；如果内存工作区中最小的比记录的元素小，则选择内存工作区中下一个相对较小但比记录的元素大的元素进行”置换“。
image.png
image.png
如果内存工作区的元素均不能被”置换“，则表明置换-选择结束。一个归并段构造完成（构造好的归并段有输出缓冲区一次性输出到硬盘中）。可以构建下一个归并段。
image.png
将内存工作区中已有的元素先执行一次”置换“。
image.png
接下了重复前面的步骤。
当初始的待排序文件全部被读入后，将内存工作区的文件输出：
image.png
最总得到如下几个归并段：
image.png
这些归并段的长度操过了内存工作区的长度。

总结

image.png