N路合并算法

Question

作为Mergesort算法的一部分，双向合并被广泛研究。但我有兴趣找出执行N路合并的最佳方法？

比方说，我有N个排序100万整数的文件。我必须将它们合并成1个文件，其中会有那些1亿排序的整数。

请记住，这个问题的用例实际上是基于磁盘的外部排序。因此，在实际场景中也会存在内存限制。因此，一次（99次）合并两个文件的天真方法是行不通的。假设每个阵列只有一个小的内存滑动窗口。

我不确定是否已经有一个标准化的解决方案来解决这个N路合并。（谷歌搜索没有告诉我太多）。

但是如果你知道一个好的n路合并算法，请张贴algo/link。

时间复杂度：如果我们大大增加了要合并的文件（N）的数量，这将如何影响算法的时间复杂度？

谢谢你的回答。

我在任何地方都没有被问过这个问题，但我觉得这可能是一个有趣的面试问题。因此标记。

Answer 1

一个简单的想法是保留要合并的范围的优先级队列，存储方式是首先从队列中删除第一个元素最小的范围。然后，您可以执行如下N路合并：

1. 将所有范围插入优先级队列，不包括空范围

这种算法的正确性本质上是证明双向合并正确工作的推广——如果你总是从任何范围中添加最小的元素，并且所有的范围都被排序，你最终会把序列作为一个整体排序。

该算法的运行时复杂性如下所示。设M是所有序列中元素的总数。如果我们使用二进制堆，那么我们从优先级队列中最多执行O（M）个插入和O（M）个删除，因为对于写入输出序列的每个元素，都有一个出列以拉出最小序列，然后是一个排队以将序列的其余部分放回队列。每个步骤都需要O（lgn）操作，因为从包含N个元素的二进制堆中插入或删除需要O（lgn）时间。这给出了一个O（mlgn）的净运行时间，它与输入序列的数量成线性关系。

也许有一种方法可以更快地实现这一点，但这似乎是一个很好的解决方案。内存使用量为O（N），因为二进制堆需要O（N）开销。如果我们通过存储指向序列的指针而不是序列本身来实现二进制堆，这应该不会有太大的问题，除非你有一个非常荒谬的序列数量要合并。在这种情况下，只需将它们合并到适合内存的组中，然后合并所有结果。

希望这有帮助！

Answer 2

搜索“多相合并”，查看经典-Donald Knuth

此外，你可能想看看由Seyedafsari提出的智能块合并

另一个有趣的理由是Kim的就地合并算法

我还推荐Vitter的这篇论文：外部内存算法和数据结构：处理海量数据。

Answer 3

以下想法如何：

1. 创建优先级队列
2. 遍历每个文件f
   1. 使用第一个值作为优先级键对（nextNumberIn（f）， f）进行排队
   1. 队列的出列头（m，f）
   2. 输出m
   3. 如果f没有耗尽
      1. 排队（下一个编号（f），f）

      因为向优先级队列添加元素可以在对数时间内完成，所以第2项是O（N×logn）。由于while循环的（几乎所有）迭代都添加了一个元素，因此整个while循环是O（M×logn），其中M是要排序的数字总数。

      假设所有文件都有一个非空的数字序列，我们有M