是先合并后排序，还是先排序后合并？

Question

我有两个没有排序的数组。将它们单独排序，然后合并，会不会更快？或者先连接数组，然后对组合后的大型数组进行排序，这样会更快吗？

Answer 1

显然，big-O在这个问题上并没有说明任何问题。假设您使用的算法是快速排序。It has a average running time of:

​

​

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

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，则排序合并将更快。

Answer 2

假设串联是在O(1)中完成的，合并需要O(n)和排序O(n log n)，您可以在以下两者之间进行选择：

排序和合并：O(n log n) + O(n) = O(n log n)

• concatenate和sort：O(1) + O((2n) log (2n)) = O(n log n)

因此，这两个选项在渐近意义上是等价的。

当然，如果使用MergeSort，那么整个讨论都是没有意义的。

Answer 3

我认为这将取决于排序算法和数据的大小。

但一个大胆的猜测是，合并然后对整个批次进行排序更可取。因为在这种情况下合并只是附加的。

而在另一种情况下，您将需要应用排序合并。