N路合并算法

Question

作为合并排序算法的一部分，双向合并被广泛​​研究。但我有兴趣找出执行 N 路合并的最佳方法？

比方说，我有 N 个文件，每个文件都对 100 万个整数进行了排序。我必须将它们合并到一个文件中，该文件将包含 1 亿个排序的整数。

请记住，此问题的用例实际上是基于磁盘的外部排序。因此，在实际场景中也会有内存限制。因此，一次(99 次)合并 2 个文件的天真方法是行不通的。假设我们只有一个小的滑动内存窗口可用于每个数组。

我不确定这个N路合并是否已经有一个标准化的解决方案。 (谷歌搜索并没有告诉我太多信息)。

但是如果你知道一个好的 n-way 合并算法，请发布算法/链接。

时间复杂度:如果我们大大增加要合并的文件数量 (N)，这将如何影响您的算法的时间复杂度？

感谢您的回答。

我在任何地方都没有被问到这个问题，但我觉得这可能是一个有趣的面试问题。因此标记。

Answer 1

下面的想法怎么样:

1. 创建一个优先级队列
   
   
2. 遍历每个文件f
   1. 使用第一个值作为优先键对 (nextNumberIn(f​​), f) 进行排队
      
      
3. 当队列不为空时
   1. 出列队列头 (m, f)
   2. 输出m
   3. 如果 f 没有耗尽
      1. 入队 (nextNumberIn(f​​), f)

由于向优先级队列添加元素可以在对数时间内完成，因此第 2 项是O(N × log N)。由于 while 循环的(几乎所有)迭代都会添加一个元素，因此整个 while 循环是 O(M × log N)，其中 M 是数字的总数排序。

假设所有文件都有一个非空的数字序列，我们有 M > N，因此整个算法应该是 O(M × log N)。