多相合并排序 - 阶段数量是多少

Question

假设我们必须在外部对一些大数字进行排序。我们要检查2个案例：

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是Fibonacci序列中的第9个数字，那么我们将有7个阶段。

但是......如果我们的运行次数不是斐波纳契数，那么必须用虚拟运行来填充磁带以获得否。达到斐波纳契数。

最后，我的问题是：

当运行次数不是斐波纳契数时，为了对序列进行排序所需的平均情况数是多少？

Answer 1

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

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

---

关于原始问题中的信息的一些注释：

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

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

由于合并了各种尺寸的先前运行，运行尺寸增加。假设运行大小为1个元素，31个运行，4个磁带。初始分配后，运行计数：运行大小为{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有一篇关于多相合并排序的文章。

https://en.wikipedia.org/wiki/Polyphase_merge_sort

---

如果预先知道总运行计数，则初始分配可以包括初始合并操作以使运行计数达到理想数量，但是现在运行大小因初始合并操作而变化，因此每个磁带最终会混合使用运行大小。同样，使用文件标记指示运行结束消除了必须跟踪内存中的运行大小。

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