为什么要使用n路合并？与2路合并相比，它有什么优势？ [英] why should we use n-way merge? what are its advantages over 2-way merge?

问题描述

我尝试阅读有关n路合并的几篇文章，但不理解这个概念。我对为什么要在2路合并中使用n路合并感到困惑？就像为什么将数组分为3部分，对它们进行排序，然后将2部分进行2路合并，然后用合并的2部分对3rd部分进行2路合并：）

I tried to read few articles on n-way merge, but did not understand the concept. I am confused on why would you use n-way merge over 2-way merge? Like why would you divide array in 3 parts, sort them then do 2-way merge of 2 parts and then 2-way merge of 3rd part with this merged 2 parts :)

谢谢

推荐答案

在常规合并排序中，将数组除以2，直到深度达到 log 2 n ，然后开始合并。大小为 m 的两个数组的每次合并也将进行 2m 个操作。

In a "normal" merge sort, you divide the array by 2, until reaching a depth of log2n and then start merging. Each merge of two arrays of size m would also take 2m operations.

这将使您得到以下公式（在时序分析中）：

This gets you to the following formula (in timing analysis):

n/2 * 2 + n/4 * 4 + ... 1 * n = n * log2n

现在，如果执行三向合并，将对数组进行分割乘以3。与先前方法的区别是双重的：

Now if you do a three-way merge, you will divide the array by 3. The difference with the previous method is twofold:

• 除法深度现在为 log 3 n 。


• 在合并过程中，您需要查找至少3个元素，而不是比较2个元素。
$ b

这意味着，在最基本的实现中，您将获得以下公式：

This means that, in the most basic implementation, you will get such a formula:

n/3 * 2*3 + n/9 * 2*9 + ... 1 * 2*n = 2 * n * log3n

请注意，将2乘以是因为找到三个元素的最小值包含2个运算。

Note that 2 is multiplied because finding the minimum of three elements consists of 2 operations.

渐近而言，这两个都是Θ（nlogn）。但是，也许在实践中（我没有尝试过），由于它的 log 3 n ，三向合并排序会带来更好的性能。不过，由于n的 log 2 n n 只等于20，而 log 3 n 等于12.5，我怀疑这种优化是否真的有效，除非 n 很大。

Asymptotically, these two are both Θ(nlogn). However, perhaps (I haven't tried) in practice the three-way merge sort would give better performance because of its log3n. Nevertheless, since log2n for n = 1000000 is a mere 20, and log3n for the same number is 12.5, I doubt this optimization would be really effective unless n is quite large.

通过巧妙的实现，k向合并可能确实会对合并排序产生很好的影响。这个想法是，一旦找到 k 个元素的最小值，您就已经知道其余 k-1 不是最小的元素。因此，一旦消耗了其相应列表中的最小值，就只需比较该列表的新值并找到其相对于其余 k-1 元素的顺序。使用堆，这将是微不足道的。

With a clever implementation, a k-way merge may indeed have a nice impact on merge sort. The idea is that once you find the minimum of k elements, you already know the relationship between the rest of the k-1 elements that are not minimum. So once consuming that minimum element from its respective list, you need only compare the new value of that list and find its ordering with respect to the remaining k-1 elements. Using a heap, this would be quite trivial.

请确保还看到杰里的答案。我同意他的观点，多路合并的真正力量来自处理多个磁盘和并行处理。

Be sure to also see Jerry's answer. I agree with him that the true power of multiway merge comes from dealing with multiple disks and parallel processing.

这篇关于为什么要使用n路合并？与2路合并相比，它有什么优势？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！