algorithm - 什么是组合预排序集的最快排序算法

假设我有一些集合，我知道它们已经被排序，比如{0,2,10,23,65}和{3,5,8..}。可以将任意数量的预排序集合并到一个排序集中的最佳排序算法是什么？这种分类有多有效？

最佳答案

你不需要分类，你需要合并。这是在O(M+N)中完成的，使用一个简单的循环，让两个索引查看两个部分的当前元素，将二者中的较小者添加到最终序列中，并将索引向前推进一个。
这是伪代码：

int[] parts1, parts2 // Sorted parts
int i = 0, j = 0;
while i != parts1.Length || j != parts2.Length
    if i != parts1.Length || j != parts2.Length
        if parts1[i] < parts2[j]
            res.Add(parts1[i++])
        else
            res.Add(parts2[j++])
    else if i != parts1.Length
        res.Add(parts1[i++])
    else
        res.Add(parts2[j++])

在每个步骤中，循环前进i或j，执行parts1.Lenght + part2.Length次。

关于algorithm - 什么是组合预排序集的最快排序算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10525638/