多向合并与双向合并

Question

当我们从外部合并排序大文件时,我们将它分成小文件,对它们进行排序,然后将它们合并回一个大的排序文件.

合并时,我们可以执行许多双向合并传递,也可以执行一次多路合并.

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

Answer 1

一种多向合并通常更好.考虑三个小文件:

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).