归并排序时间复杂度

画个图：

          n
       /    \
     n/2     n/2
    /  \      /  \
  n/4   n/4   n/4   n/4
  / \   / \   / \   / \
 n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8

树高logn,每层加起来都是n,一共是logn×n
上面是n为2的幂时的特殊情况.对于一般情况,同样可证.

这里需要用一些数学公式：

1. 设数组的长度为N，用 T(N) 表示排序一个长度为N的数组所需要的比较次数，可想而知，T(0) 和 T(1) 为0
2. 将数组的两边分别排序各需要 N/2 次比较（上限），归并所需次数为N（上限）
3. 所以 T(N) ≤ T(N/2) + T(N/2) + N
4. 设 N = 2n且不等式的等号成立：T(2n) = 2T(2n-1) + 2n(N / 2 = 2n - 1)
5. 等式两边同时除以2n，得到：T(2n) / 2n = T(2n-1) / 2n - 1 + 1
6. 由上式可以得到：T(2n - 1) / 2n - 1 = T(2n-2) / 2n - 2 + 1
7. 将 6 的结果代入 5 中，得到：T(2n) / 2n = T(2n-2) / 2n - 2 + 1 + 1
8. 重复第7步，直到得到如下结果：T(2n) / 2n = T(20)/20 + n（共计 n - 1 步）
9. 等式两边同时乘以 2n ，得到结果：T(N) = 2n T(20) + n 2n = NlogN( n = logN)
   所以，算法复杂度为O(nlogn)