[科普中国]-磁带文件排序

磁带文件的排序过程类似于磁盘文件的排序过程，步骤如下：

（1）把文件的记录分段输入内存进行内部排序，生成若干个有序段并把它们写到磁带上；

（2）对这些有序段进行反复合并；

（3）最后将有序段合并成一个包含文件中所有记录的有序段。

至此，文件的外部排序过程就结束了。1

因为磁带是顺序存取的设备，存取数据快的时间与所存取的数据块在磁带上的位置有密切关系，所以有序段分布在不同磁带上和在同一磁带的不同位的情况对排序的效率有很大的影响。1

所谓平衡排序是指在排序的过程中，进行下一遍合并之前必须把初始有序段或上一遍合并所产生的有序段均匀地分布到各输入带上。1

与磁盘文件的排序一样，对磁带文件进行排序所需要的时间与扫描磁带文件的遍数有密切关系，采用k（≥2）路合并可以减少扫描磁带文件的遍数。1

为了避免太多的磁带寻找时间，当前被合并的有序段必须放在各台不同的磁带机上。因此，k路合并在合并期间至少需要k台磁带机作为输入。另外还需要一台作为输出。这样，进行k路合并至少要有（k+1）台磁带机。如果用（k+1）台磁带机实现k路合并，那么需要对输出带另外做一遍扫描，把上一遍合并时所生成的有序段均匀地分布到k台机上作为下一遍合并之用。如果使用2k台就可以避免上述的重新分布有序段的问题，因为进行k路合并时，可用其中k台作为输入，而其余k台作为输出。在对文件进行下一遍合并时把输出带作为输入带，而把输入带作为输出带。1

如果使用k路合并，那么为了避免对输出有序段重新分布所进行的扫描，就需要有2k台磁带机。如果利用k阶斐波那契数列的特性，对k路合并来讲，只需要（k+1）台就可以避免对输出有序段重新分布所进行的扫描。1

在这里，我们假定初始有序段的长度为可在内存进行一次内部排序的记录个数，随着合并的进行，新产生的有序段的长度也逐渐增加。我们用记号表示在某台磁带机目前有n个有序段，其中每个有序段的长度等于s个初始有序段长度之和。如果每个初始有序段有1个记录，那么这台机上共有1×s×n个记录。1

现在已k=2为例说明多阶段合并排序的执行过程。对于两路合并来讲，需要三台磁带机，记为。如果输入文件可在内存用内部排序产生21个初始有序段，那么多阶段合并排序的过程可由七个阶段所组成：

（1）从输入文件产生21个初始有序段，并把13个初始有序段分布在上，把8个初始有序段分布在上，目前是空带。这样，上有个记录，上有个记录，而上没有记录。

（2）把上的个记录与上的个记录个记录合并，把合并后的个记录送，这时剩下个记录，变成空带。

（3）把上的个记录与上的个记录个记录合并，把合并后的个记录送，这时剩下个记录，变成空带。

（4）把上的个记录与上的个记录个记录合并，把合并后的个记录送，这时剩下个记录，变成空带。

（5）把上的个记录与上的个记录个记录合并，把合并后的个记录送，这时剩下个记录，变成空带。

（6）把上的个记录与上的个记录个记录合并，把合并后的个记录送，这时剩下个记录，变成空带。

（7）把上的个记录与上的个记录个记录合并，把合并后的个记录送，这时和都变成空带，合并排序的过程结束。1

由上述过程可知，除最后阶段外，在其余各个阶段中有且只有一台磁带机变成空带，且各阶段的空带的台号依次取3,2,1循环轮换的。上一阶段出现的空带正好作为下一阶段的输出带，这样就避免了有序段的重新分布。同时，各台非空磁带参加合并的有序段的个数就是这些磁带中具有最少有序段的个数，因此执行某个阶段之后必定出现一台空带。在各阶段中，各台非空的磁带机参加合并的有序段的个数正好是某个斐波那契数。如果上一阶段各台非空的磁带机参加合并的有序段个数是，那么下一阶段各台非空磁带机参加合并的有序段个数是。

实现正确合并的关键在于选择一种正确的初始有序段的分布，为此，我们先以k=2的情况为例找出一般的规律，然后在加以推广。1

一般来说，对于（k+1）台磁带机的k路多阶段合并排序和指定的n来说，分布在第i（1≤i≤k）台上的初始有序段的个数为：

（1）当n=0时，；

（2）当n>0时，。

而k台上的初始有序段的总数为。1