归并排序涉及递归到了递归，通过这篇博客，可以看下如何分析递归的时间复杂度。

一个问题 a 可以分解成多个子问题 b，c，可以得到下面的公式

T(a) = T(b) + T(c) + K

假设对 n 个元素进行归并排序，需要的时间为 T(n)。分解成两个子数组后，那么每个子数组的排序需要的时间就为 T(n/2)。而合并两个有序子数组的时间复杂度为 O(n)。所以归并排序的时间复杂度计算公式为

T(1) = C；   n=1 时，只需要常量级的执行时间，所以表示为 C。
T(n) = 2*T(n/2) + n； n>1

因为 T(n/2) = 2 * T(n/4) + n/2，所以

T(n) = 2 * (2 * T(n/4) + n/2) + n
     = 2^2 * T(n / 2^2) + 2 * n

根据 T(n/4) = 2 * T(n/8) + n/4，可以得到

T(n) = 2^3 * T(n / 2^3) + 3 * n

以此类推，可以知道

T(n) = 2^k * T(n / 2^k) + k * n

当 T(n / 2^k)=T(1)，也就是 n / 2^k = 1，则 k = logn （这里 log 的 base 是 2）。把 k 的值代入上面的公式，可以得到 T(n)=Cn+nlogn，用大 O 标记就是 O(nlogn)。