合并k个排序数组 - 优先队列 vs 传统归并排序，何时使用哪种？

Question

假设我们有k个已排序的数组（每个大小为n），在什么情况下使用优先级堆比传统合并（类似于归并排序中使用的方法）更好，反之亦然？

优先队列方法：这种方法中，我们有一个初始大小为k的小根堆（最初，将来自每个数组的第一个元素添加到堆中）。现在，我们删除最小元素（来自一个输入数组），将其放入最终数组中，并插入同一输入数组中的新元素。这种方法需要O(knlogk)时间和O(kn)空间。注意：它需要O(kn)的空间，因为这是最终数组的大小，在计算渐近空间复杂度时，它支配着堆的大小。

传统合并：在这种方法中，我们合并前两个数组以获得大小为2n的排序数组。我们对所有输入数组重复此过程，第一次通过后，我们获得k/2个大小为2n的排序数组。我们重复此过程直到获得最终数组。每次通过的时间复杂度为O(kn)，因为每次比较后都会将一个元素添加到相应的输出数组中。我们有log k次通过。因此，总时间复杂度为O(kn log k)。而且由于我们可以在每次通过后删除输入数组，所以在任何时候使用的空间为O(kn)。

正如我们所看到的，两种方法的渐近时间和空间复杂度都完全相同。那么，什么情况下我们会更喜欢其中一种？我知道对于外部排序，优先队列方法更好，因为您只需要占用O(k)内存空间，并且可以将每个元素从磁盘读取并写回磁盘。但是当我们有足够的内存时，这些方法又如何相互比较呢？

- Marko Cain

Answer 1

操作的总数，包括比较和移动，两种方法大致相同。k路归并需要更多的比较但是移动次数更少。我的系统有一个8路缓存（Intel 3770K 3.5 GHz），在4路合并排序的情况下，为4个输入运行提供了4行缓存以及1行缓存用于合并后的输出运行。在64位模式下，有16个寄存器可用于工作变量，其中8个用于指向每个“运行”当前位置和结束位置的指针（编译器优化）。

在我的系统上，我比较了4路合并（无堆，每移动一个元素约3次比较）与2路合并（每次移动一个元素约1次比较，但要经过两倍的通道数）。4路合并比较次数增加了1.5倍，但移动次数减少了0.5倍，因此基本上操作次数相同，但由于缓存问题，4路合并速度约快15％。

我不知道16个寄存器是否足够使6路合并略微更快，而且16个寄存器对于8路合并来说不足（一些工作变量将基于内存/缓存）。尝试使用堆可能也没有帮助，因为堆将基于内存/缓存（而不是基于寄存器）。

k路归并主要用于外部排序，其中比较时间由于更大的移动开销而被忽略。

- rcgldr