假设我们给出了k排序数组（每个大小为n），在这种情况下使用优先级堆比传统合并更好（类似于merge-sort中使用的那个），反之亦然？
优先级队列方法：在这种方法中，我们有一个大小为k的最小堆（最初，每个数组的第一个元素被添加到堆中）。我们现在删除min元素（来自其中一个输入数组），将其放在最终数组中并从同一输入数组中插入一个新元素。这种方法需要O(kn log k)时间和O(kn)空间。注意：它需要O(kn)空间，因为这是最终数组的大小，这在计算渐近空间复杂度时支配堆的大小。
传统合并：在这种方法中，我们合并前两个数组以获得大小为2n的排序数组。我们对所有输入数组重复此操作，在第一次传递后，我们获得k/2排序的数组，每个数组的大小为2n。我们重复这个过程，直到得到最终的数组。每次传递都具有O(kn)的时间复杂度，因为在每次比较之后将一个元素添加到相应的输出数组中。我们有记录k遍。所以，总时间复杂度是O(kn log k)。由于我们可以在每次传递后删除输入数组，因此任何一点使用的空间都是O(kn)。
我们可以看到，这两种方法的渐近时间和空间复杂度完全相同。那么，什么时候我们更喜欢一个而不是另一个呢？我理解，对于外部排序，优先级队列方法更好，因为您只需要O(k)内存空间，并且您可以从磁盘读取和写入每个元素。但是，当我们有足够的内存时，这些方法如何相互叠加？
操作总数，比较+移动，两种方式大致相同。 k-way合并比较多，但移动次数较少。我的系统有一个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-way合并主要用于外部排序，其中由于更大的移动开销而忽略比较时间。