3的多相排序和合并顺序

Question

关于多相排序的简单问题。您是否按顺序写入文件？像这样：

F1：10 13 7 8 9 4 3 17 18 2

F2：-

F3：-

F4：-

这个：

F1：-

F2：10 13 7 8

F3：9 4 3 17

F4：18 2

或者你交替吗？与这个？

F1：-

F2：10 8 3 2

F3：13 9 17

F4：7 4 18

还是不重要？

Answer 1

对于任何特定的输入集，您选择如何分割初始输入肯定会影响在某些情况下需要进行的传递次数，但从一般意义上来说，这应该不重要 - 有些会稍微好一些一种方法优于另一种方法，有些会稍微差一些。最终所有可能输入的平均情况将是相同的。

但是，第二种方法的优点是，您不必预先扫描输入来计算元素数，从而确定每个存储桶中应放入多少元素。