合并排序究竟有多少比较？

Question

我已经读过,quicksort在实践中比mergesort快得多,其原因是隐藏的常量.那么,随机快速排序复杂度的解决方案是2nlnn = 1.39nlogn,这意味着快速排序中的常数是1.39.但是mergesort怎么样？mergesort中的常量是什么？

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

令人印象深刻的是,这比quicksort 更好!那么为什么在地球上快速排序比合并排序更快？这与其他与比较次数无关的因素有关.首先,由于快速排序在合并排序不合适的情况下就位,因此合并排序中的引用位置与快速排序中的位置差不多.这是一个非常重要的因素,因为快速排序在实践中比合并排序要好得多,因为高速缓存未命中的成本非常高.此外,对数组进行排序所需的时间不仅要考虑比较次数.其他因素,例如每个数组元素移动的次数也很重要.例如,在合并排序中,我们需要为缓冲元素分配空间,移动元素以便它们可以合并,然后合并回数组.我们的分析中没有计算这些动作,但它们肯定会加起来.将此与quicksort的分区步骤进行比较,该步骤将每个数组元素移动一次并保持在原始数组中.这些额外的因素,而不是所做的比较次数,在算法的运行时间占主导地位.

这个分析比最优分析要精确一点,但维基百科确认分析大致为n lg n,这确实比quicksort的平均情况更少.

希望这可以帮助!

Answer 2

在最坏的情况下，假设一个直接的实现，排序n 个元素的比较次数是

n ? lg n ? ? 2 ^{?lg n ?} + 1

其中LG Ñ表示基数2的对数的Ñ。

这个结果可以在相应的维基百科文章或唐纳德·克努斯 (Donald Knuth)的计算机编程艺术的最新版本中找到，我刚刚写下了这个答案的证明。