多阶段合并排序-阶段数是多少？

Question

假设我们必须从外部排序一些大的数字。我们要审查两个案件：

1. 4盘磁带:2盘输入磁带，2盘输出
2. 3盘磁带:2英寸，1盘

案例1：

​

​

我们从k运行开始，然后将这些运行复制到2个输入磁带(在下面的图中左边)，每次迭代我们从输入磁带中进行两次不同的运行，合并(和排序)它们，在一次迭代中将它们保存到第一个输出磁带，在下一个迭代中保存到第二个输出磁带，如下所示。然后，我们切换输出磁带与输入的，并重复这个过程。因此，如果我们有，比方说，n=10^6元素和k=1000运行，那么在第一个阶段之后，运行的大小将是2000，在第三个4000之后，等等。所以相的总数是ceil(log_2(n))。

案例2：

​

​

在最好的复杂情况下，阶段的数目是position of Fibonacci’s number in the Fibonacci’s sequence minus two，也就是说，如果我们的初始运行次数是k=34，而34是斐波那契序列中的第9个数，那么我们将有7个阶段。

​

但是…如果我们的运行次数不是Fibonacci数，那么就必须用虚拟运行来填充磁带，这样才能得到no。直到斐波纳契数。

最后，我的问题是：

当运行次数不是斐波那契数时，排序序列所需的平均阶段数是多少？

Answer 1

有多少阶段..。当运行次数不是斐波那契数时？

如果运行计数不是理想的数字，那么排序将需要一个额外的阶段，类似于将运行计数舍入到下一个理想数。虚拟运行不需要占用磁带上的任何空间，但是在非理想发行版的一个阶段中，代码必须处理多个磁带上的数据结束。

关于原问题中的信息的一些注意事项：

4磁带示例显示了平衡的双向合并排序。对于多阶段合并排序，每个阶段只有一个输出磁带。对于4个磁带驱动器，初始设置在其他3个驱动器之间运行，因此在初始分发之后，始终是3个输入磁带，1个输出磁带。

Fibonacci数只适用于3磁带场景。对于4或更多的磁带场景，从最后阶段开始并向后工作最容易生成序列。对于4个磁带上的31次运行，最后运行计数为{1,0,0,0}，向后运行：{0,1,1,1}，{1，02，2}，{3,2,0,4}，{7，6，4}，{0,13,11,7}。

由于合并以前不同大小的运行，运行大小会增加。假设运行大小为1元素，31次运行，4次磁带。初始分发后，运行计数: run size为{0:0、13:1、11:1、7:1}。第一阶段：{7:3,6:1,4:1,0:0}。第二相：{3:3,2:1,0:0,4:5}。第三相{1:3,0:0,2:9,2:5}。第四阶段：{0:0,1:17,1:9,1:5}。第五和最后阶段{1:31，0:0，0:0:0:0}。

跟踪运行大小会变得非常复杂，因此磁带的一个简单解决方案是使用单个文件标记表示运行结束，使用双文件标记表示数据结束。

Wiki有一篇关于多阶段合并排序的文章。

sort

如果预先知道总运行计数，则初始发行版可以包括初始合并操作，以使运行计数达到理想的数目，但现在运行大小因初始合并操作而不同，因此每个磁带都以混合运行大小结束。同样，使用文件标记来指示运行结束，可以避免在内存中跟踪运行大小。

多阶段合并排序是使用3个堆栈进行排序的最快方法。