为何归并排序最坏情况也满足Omega(nlog(n))？

直观解释 #

归并排序的核心逻辑是分治拆分+有序子数组合并：

• 不管输入数组是什么情况（包括最坏情况），都必须把原数组逐层拆分成单个元素，这个拆分过程会产生log₂n层递归（非2的幂时层数为⌈log₂n⌉，量级一致）。
• 每一层递归中，所有子数组的总长度都是n，归并操作必须处理每一个元素——哪怕是最坏情况（比如两个子数组元素交替大小），每一层的归并也至少要完成n次元素移动/赋值，且比较次数的下限是线性的（比如一个子数组全小于另一个时，也需要至少n/2次比较完成归并）。
• 总共有logn层，每层至少需要线性时间，因此整体时间复杂度的下界是nlogn，也就是Ω(nlogn)。

数学推导 #

我们用递归式和数学归纳法严谨证明：

递归式定义 #

归并排序的时间复杂度递归式为：
T(n) = 2T(n/2) + C(n)
其中：

• T(n)表示排序长度为n的数组的时间；
• C(n)是归并两个长度为n/2的有序子数组的时间（最坏情况下）。

确定C(n)的下界 #

归并两个长度均为n/2的子数组时，无论元素如何分布，至少需要n/2次比较：

• 归并过程中，每次比较至少能确定一个元素的最终位置；
• 即使其中一个子数组的所有元素都小于另一个，也需要比较n/2次（取出较小子数组的所有元素后，直接追加较大子数组）；
• 因此C(n) ≥ n/2（对于n≥2）。

数学归纳法证明 #

我们要证明存在常数c>0，使得对于所有n≥1，T(n) ≥ c·nlogn。

1. 基例：当n=1时，T(1)=0，而c·1·log1=0，显然成立。
2. 归纳假设：假设对于所有k <n，T(k) ≥ c·klogk成立。
3. 归纳步骤：
   将递归式代入归纳假设：

T(n) = 2T(n/2) + C(n)
≥ 2·c·(n/2)log(n/2) + n/2
= c·n(logn - log2) + n/2
= c·nlogn - c·n + n/2

要让T(n) ≥ c·nlogn，只需满足：
-c·n + n/2 ≥ 0
取c=1/4，则：
- (1/4)n + n/2 = n/4 ≥0，对所有n≥1成立。

因此T(n) ≥ (1/4)nlogn，即归并排序在最坏情况下的时间复杂度满足Ω(nlogn)。

结合已知的最坏情况下O(nlogn)的结论，可得出归并排序最坏情况下的时间复杂度为Θ(nlogn)。

内容的提问来源于stack exchange，提问作者newbieCoder