c# - 理解和解决 K-Way 归并排序

Question

我想:

1. 计算 k 路归并排序对数字从 0 到 N-1 的随机排列进行排序所需的比较次数。

2. 计算 K-Way 归并排序对数字从 0 到 N-1 的随机排列进行排序所需的数据移动次数。

我了解 2 向归并排序如何正确工作，并且非常了解代码。我现在的问题是我不知道如何开始。如何将 2-way 归并排序转换为 K-Way 才能解决上述问题？

我在网上搜索过，但找不到任何教程来很好地解释“k-Way 归并排序”。

我需要很好的解释该做什么，以便我可以从那里得到它并自己做。

就像我说的，我了解 2-Way，那么我如何转向 K-Way 归并排序？我如何实现 K-way？

编辑

我读了一些帖子 http://bchalk.com/work/view/k_way_merge_sort必须使用 BinaryHeap 来实现 k-Way 合并。是这样还是有其他方法？

如何将我的列表分成 K 个？有什么特殊的方法吗？

Answer 1

当 k > 2 时，每个输入流的前导元素通常保存在最小堆结构中。这使得查找 n 值的最小值、将该值从堆中弹出并从相应的输入流中插入替换值变得容易。

堆为每次插入执行 O(lg2 k) 比较，因此 n 项的 k 路合并的总工作量为 n * lg2(k) .

即使您询问了 C# 和 Java，您也可以通过查看用于 k 向合并的 Python 标准库代码来了解如何做到这一点:http://hg.python.org/cpython/file/2.7/Lib/heapq.py#l323

要回答您的其他问题，没有特殊的方法可以将您的列表分成 K 组。只需取第一个数组中的前 N/k 个元素，接下来的 N/k 个元素放入下一个，依此类推。对每个数组进行排序，然后使用上面提到的堆合并它们。