合并然后排序,排序然后合并是否更快？

Question

我有2个未排序的数组.将它们单独排序然后合并它们会更快吗？或者首先连接数组并对组合的巨大数组进行排序会更快吗？

Answer 1

假设连接完成O(1),合并获取O(n)和排序O(n log n),您可以选择:

• 排序和合并: O(n log n) + O(n) = O(n log n)
• 连接和排序: O(1) + O((2n) log (2n)) = O(n log n)

因此,渐近两种选择都是等价的.

当然,如果你使用MergeSort,整个讨论都是没有意义的.

Answer 2

显然，big-O 在这个问题上并没有真正说什么。假设您使用的算法是快速排序。它的平均运行时间为：

所以现在，如果排序然后合并我们得到：

f1 = 1.39n * log(n) * 2 + 2n

合并然后排序：

f2 = n + 1.39 * 2n * log(2n)

区别在于

f2 - f1 = -n + 2.78n > 0

一般情况下，如果排序算法具有复杂性

C = k * nlog(n)

然后，由于 k 通常应大于 1，并且不太可能接近 0.5，因此如果假设合并成本最多为 2n，则排序然后合并会更快。