当输入规模非2的幂时，归并排序时间复杂度的证明方法

实际归并排序的递推式应该修正为：
T(n) = T(⌊n/2⌋) + T(⌈n/2⌉) + O(n)（n>1），T(1) = O(1)
因为当n不是2的幂时，拆分后的两个子数组长度会是一奇一偶，用向下取整和向上取整才能准确描述。下面用三种方法证明其时间复杂度为O(nlogn)：

方法一：数学归纳法 #

假设存在常数C、D，使得对所有k < n，都有T(k) ≤ Ck logk + D。现在证明T(n)也满足这个不等式：

1. 展开递推式：T(n) = T(⌊n/2⌋) + T(⌈n/2⌉) + an（a是O(n)项的常数系数）
2. 代入归纳假设：
   T(n) ≤ C⌊n/2⌋log⌊n/2⌋ + D + C⌈n/2⌉log⌈n/2⌉ + D + an
3. 用⌊n/2⌋ ≤ n/2、⌈n/2⌉ ≤ (n+1)/2做放缩，结合log函数的单调性：
   当n≥2时，⌊n/2⌋log⌊n/2⌋ + ⌈n/2⌉log⌈n/2⌉ ≤ (n/2)log(n/2) + ((n+1)/2)log((n+1)/2)
4. 化简右侧式子：
   展开后可推导得到其小于等于n logn - n/2 log2 + (1/2)log((n+1)/2)，再结合n≥2时的边界条件，只要取足够大的C（比如C≥2a），就能让整个式子满足T(n) ≤ Cn logn + D，归纳成立。

方法二：递归树扩展分析 #

不用局限于每层都是等长的子数组，直接看递归树的高度和每层工作量：

• 递归树的高度h：对于任意n，log₂n ≤ h ≤ log₂n + 1。因为每次拆分至少会让一个子数组长度≤n/2，最多经过log₂n+1层就会递归到长度为1的叶子节点。
• 每层的总工作量：不管怎么拆分，每一层所有子数组的合并总操作数都是O(n)（因为所有子数组的总长度始终是n，合并的总比较、移动次数和总长度正相关）。
• 总工作量就是层数×每层工作量，即O(n × h) = O(n logn)，因为h是O(logn)量级。

方法三：主定理直接应用 #

主定理专门处理这类分治递推式，且不需要n是b的幂：
对于递推式T(n) = aT(n/b) + f(n)，这里a=2（每次拆分为2个子问题），b=2（子问题规模约为原问题的1/2），f(n)=Θ(n)。
主定理的Case 2：当f(n) = Θ(n^log_b a)时，T(n) = Θ(n^log_b a logn)。这里log_b a = log₂2 = 1，n^1 = n，正好满足f(n)=Θ(n)，因此直接得出T(n) = Θ(n logn)，自然也满足O(nlogn)。

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