算法-对"n“输入文件进行排序并生成单个输出文件的最佳方法是什么？

Question

我正在研究以下算法：

程序输入： "n“输入文件包含数字，并假设每个输入文件都是排序的。

输出到编程：以排序方式包含所有元素的单个输出文件

例如：

N=4

file1 = 1,5,6,9

file2 = 2,8,10,15

file3 =3，7，9 11

file4 = 2,4,6,8

产出= 1,2,2,3,4,5,6,6,7,8,8,9,9,10,11,15

My方法：读取每个文件的第一个元素，找到其中的最小元素并将其写入输出文件。然而，非常慢，并且有一组约束被绑定：

内存：程序需要可伸缩，文件大小可以扩展到1.4GB，所以在内存中读取整个文件是不可取的。

文件数量：文件的数量可以增长到一个大的数目，这进一步导致性能的损失。

我正在使用C编程语言来做这件事，所以请给出相应的建议，我不能改变我的语言。

Answer 1

如果已对文件进行排序，则使用合并排序的版本，这需要时间O(n)来合并已排序的集合。获取前两个列表并合并它们，然后继续这样做，直到没有剩下的文件。

这需要时间等于O(nm)，其中n是文件的大小，m是文件的数量。

希望这能有所帮助！