多路归并 vs 二路归并

Question

10

当我们对一个大文件进行外部归并排序时，我们将其分成小文件，对这些小文件进行排序，然后将它们合并回一个大的有序文件。

在合并时，我们可以进行多个二路合并或者一次多路合并。

我想知道哪种方法更好？为什么？

- KFL

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- phs · Accepted Answer

一般来说，使用多路归并更好。考虑三个小文件：

a1
a2
a3

并且

b1
b2
b3

最后的内容如下：

最后

c1
c2
c3

如果您将 a 和 b 进行合并，我们就剩下了（比方说）：

a1
b1
a2
b2
b3
a3

并且

c1
c2
c3

一种最终合并的方法会创建排序后的列表。但请注意，在此最终合并中，我们必须再次访问“a”和“b”项。这种重新合并在级联双向合并中是浪费的。

相反，您可以使用单个多路合并，但要小心如何操作。具体来说，避免使用扫描每个游标以查找最小值的幼稚双重循环。改用最小堆。这将将复杂度降回O(n log n)。