作为Mergesort算法的一部分,广泛研究了双向合并.但我有兴趣找出一个可以执行N路合并的最佳方式吗？
可以说,我有一些N文件,每个文件已经排序了100万个整数.我必须将它们合并为1个单独的文件,这将有1亿个排序整数.
请记住,此问题的用例实际上是基于磁盘的外部排序.因此,在实际场景中也会存在内存限制.因此,一次合并2个文件(99次)的天真方法将无效.假设我们每个阵列只有一个小的可用内存滑动窗口.
我不确定是否已经存在这种N路合并的标准化解决方案.(谷歌搜索并没有告诉我太多).
但是如果你知道一个好的n路合并算法,请发布algo/link.
时间复杂度:如果我们大大增加N要合并的文件()的数量,那将如何影响算法的时间复杂度？
谢谢你的回答.
我没有被问过这个问题,但我觉得这可能是一个有趣的面试问题.因此标记.