algorithm - 归并排序究竟进行了多少次比较？

Question

我读到在实践中快速排序比归并排序快得多，原因是隐藏常量。

那么，随机快速排序复杂度的解是 2nlnn=1.39nlogn，这意味着快速排序中的常数是 1.39。

但是合并排序呢？归并排序中的常量是什么？

Answer 1

让我们看看能否解决这个问题!

在合并排序中，在递归的每个级别，我们执行以下操作:

1. 将数组分成两半。
2. 对每一半进行递归排序。
3. 使用合并算法将两半合并在一起。

那么每一步要进行多少次比较呢？好吧，除法步骤不做任何比较；它只是将数组分成两半。第 2 步不(直接)进行任何比较；所有比较都是通过递归调用完成的。在第 3 步中，我们有两个大小为 n/2 的数组，需要合并它们。这最多需要 n 次比较，因为合并算法的每一步都进行一次比较，然后消耗一些数组元素，所以我们不能进行超过 n 次比较。

将这些结合在一起，我们得到以下重复:

C(1) = 0
C(n) = 2C(n / 2) + n

(如评论中所述，线性项更准确地说是 (n - 1)，尽管这不会改变总体结论。我们将使用上述递归作为上限。)

为了简化这个，让我们定义 n = 2^k 并根据 k 重写这个循环:

C'(0) = 0
C'(k) = 2C'(k - 1) + 2^k

这里的前几项是 0, 2, 8, 24, ... 。这看起来有点像 k 2^k，我们可以通过归纳来证明这一点。作为我们的基本情况，当 k = 0 时，第一项为 0，k 2^k 的值也为 0。对于归纳步​​骤，假设声明对某些 k 成立并考虑 k + 1.那么值为2(k 2^k) + 2^{k + 1} = k 2 ^{k + 1} + 2^{k + 1} = (k + 1)2^{k + 1}，所以对于 k + 1 的说法成立，完成归纳。因此 C'(k) 的值为 k 2^k。由于 n = 2 ^k，这意味着，假设 n 是 2 的完美幂，我们有进行比较的次数是

C(n) = n lg n

令人印象深刻的是，这比快速排序更好!那么到底为什么快速排序比归并排序快呢？这与与比较次数无关的其他因素有关。首先，由于快速排序在适当的地方工作，而归并排序在不适当的地方工作，因此归并排序中的引用局部性不如在快速排序中那么好。这是一个如此巨大的因素，以至于在实践中快速排序最终比合并排序好得多，因为缓存未命中的成本非常高。此外，对数组进行排序所需的时间不仅仅考虑比较次数。其他因素(如每个数组元素移动的次数)也很重要。例如，在合并排序中，我们需要为缓冲的元素分配空间，移动元素以便它们可以合并，然后合并回数组。我们的分析中没有计算这些 Action ，但它们肯定加起来了。将此与快速排序的分区步骤进行比较，它只移动每个数组元素一次并保留在原始数组中。这些额外的因素，而不是进行比较的次数，决定了算法的运行时间。

此分析比最佳分析精确一些，但是 Wikipedia确认分析大致为 n lg n，这确实比快速排序的平均情况下的比较少。

希望这对您有所帮助!