上一篇归并排序是基于分而治之的思想，通过递归调用自身来完成排序的。 本文是关于归并排序的最后一部分——分析其时间复杂度。

这个过程将解释如何生成各种时间复杂度中常见的符号 - “lgn”（以 2 为底的对数函数）。

递归

代码分析

对合并排序代码执行逐行分析。 当元素个数n>1时，分解运行时间如下：

分解：第1行是判断，第2行是分解步骤（只计算中间位置），两者都需要常数时间，所以D1(n) = θ(1)，D2(n) = θ(1)。

解：将原问题分解为2个子问题，每个子问题的大小为原问题的1/2。 为了解决大小为 n/2 的子问题，第 3 行和第 4 行各需要 T(n/2) 时间，因此解决这两个子问题总共需要 2T(n/2) 时间。

合并：在合并算法中，已知有n个元素的数组上的两个子数组的MERGE需要花费θ(n)时间，即第5行C(n) = θ(n)。

添加每行的执行时间：

T(n) = 2T(n/2) + D1(n) + D2(n) + C(n)（当 n > 1 时）

T(n)的表达式中也包含T，因此上式称为T(n)的递归公式。

根据分析化简可得：

T(n) = 2T(n/2) + θ(n)（当 n > 1 时）

求解递归表达式

求解递归公式就是获得描述T(n)与输入尺度n之间关系的函数表达式的过程。 为了方便起见，假设 n 恰好是 2 的幂（子数组始终可被 2 整除，直到只有 1 个元素）。 该假设不影响递归解的增长幅度。

将递归公式改写为：T(n) = 2T(n/2) + cn（当n > 1时），然后手绘出“递归”是如何一层层展开的——递归树：

构造递归树

通过这样逐层递归展开，得到一棵完整的递归树如下：

完全递归树

将递归公式完全展开后，就形成了一棵完整的递归树，共有lgn+1层（如果n为8，则树有lg8+1=4层）。 每层的成本为 cn，因此总成本为 cnlgn+cn ，忽略低阶项和常数 c，即 T(n) = θ(nlgn)。

关于 θ(nlgn)

现在我们知道时间复杂度中的 lgn 是如何生成的：它基于递归。

lgn，log2n，是一个以 2 为底的对数函数，它的增长速度比任何线性函数都慢，所以在最坏的情况下，输入足够大，运行时间为 θ(nlgn) 的合并排序会比插入排序更好运行时间为 θ(n2)。

y=x 且 y=lgx