归并排序

核心思想

拆分 - 排序 - 聚合
image.png

代码实现

时间复杂度

我们假设对 n 个元素进行归并排序需要的时间是 T(n)，那分解成两个子数组排序的时间都是 T(n/2)。我们知道，merge() 函数合并两个有序子数组的时间复杂度是 O(n)。所以，套用前面的公式，归并排序的时间复杂度的计算公式就是：

  1. T(1) = C；   n=1时，只需要常量级的执行时间，所以表示为C。
  2. T(n) = 2*T(n/2) + n； n>1
  1. 求解 T(n):
T(n) = 2*T(n/2) + n
     = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
     = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
     = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
     ......
     = 2^k * T(n/2^k) + k * n
     ......

通过这样一步一步分解推导，我们可以得到 T(n) = 2^kT(n/2^k)+kn。当 T(n/2^k)=T(1) 时，也就是 n/2^k=1，我们得到 k=log2n 。我们将 k 值代入上面的公式，得到 T(n)=Cn+nlog2n 。如果我们用大 O 标记法来表示的话，T(n) 就等于 O(nlogn)。所以归并排序的时间复杂度是 O(nlogn)。排序方法稳定，所以任何情况下时间复杂度都相同。

空间复杂度

由于空间可以复用，而每个函数执行时申请的临时内存空间不会大于 n ，故空间复杂度为 O(n)。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。