mergesort - 为什么归并排序的最坏情况仍然是 n log n？

Question

这是我之前参加的期末考试的一个问题，我不知道如何回答。

那是

什么是合并排序的最坏情况运行时，但更重要的是，为什么？

Answer 1

分而治之贡献了一个 log(n) 因子。您将数组分成两半 log(n) 次，每次这样做时，对于每个段，您必须对两个排序数组进行合并。合并两个排序数组是 O(n)。该算法只是走上两个数组，然后走上滞后的那个。

Answer 2

你得到的递归是 r(n) = O(n) + r(roundup(n/2))+r(rounddown(n/2)。问题是你不能使用 Masters Theorem 来解决这个问题，因为四舍五入。因此，您可以进行数学运算或使用类似 hack 的解决方案。如果您的输入不是两个数字的幂，只需“放大”即可。然后您可以在 r(n) = O 上使用大师定理(n) + 2r(n/2)。显然这会导致 O(nlogn)。函数 merge() 本身在 O(n) 中，因为在最坏的情况下，您需要进行 n-1 次比较。