今天面试的时候，被问到归并排序的时间复杂度，这个大家都知道是O（nlogn），但是面试官又继续问，怎么推导出来的。这我就有点懵了，因为之前确实没有去真正理解这个时间复杂度是如何得出的，于是就随便答了一波（理解了之后，发现面试的时候答错了......）。

  归并排序和快速排序，是算法中，非常重要的两个知识点，同时也是在面试中被问的非常频繁的内容，我明知如此，却没有彻底理解，真是太不应该了。所以，今天这篇博客就来分析一下这两种排序算法的时间复杂度是如何得出的。我查了许多篇博客，很多都是通过公式进行分析，十分难理解，下面我就结合自己的理解，使用通俗易懂的方式进行描述（为了好理解，可能会有些啰嗦）。

  了解归并排序的应该都知道，归并排序的时间复杂度是O（nlogn），且这个时间复杂度是稳定的，不随需要排序的序列不同而产生波动。那这个时间复杂度是如何得来的呢？我们可以这样分析，假设我们需要对一个包含n个数的序列使用归并排序，并且使用的是递归的实现方式，那么过程如下：

  ......

  我们知道，归并排序的过程中，需要对当前区间进行对半划分，直到区间的长度为1。也就是说，每一层的子区间，长度都是上一层的1/2。这也就意味着，当划分到第logn层的时候，子区间的长度就是1了。而归并排序的merge操作，则是从最底层开始（子区间为1的层），对相邻的两个子区间进行合并，过程如下：

  ......

  通过上面的过程我们可以发现，对于每一层来说，在合并所有子区间的过程中，n个元素都会被操作一次，所以每一层的时间复杂度都是O（n）。而之前我们说过，归并排序划分子区间，将子区间划分为只剩1个元素，需要划分logn次。每一层的时间复杂度为O（n），共有logn层，所以归并排序的时间复杂度就是O（nlogn）。

  上面的描述算是非常详细了，应该不会太难理解。如果上面的过程还是不太理解，那么我们通过另外一种更直观的方式进行分析。上面描述的是递归的过程，下面我们通过非递归（迭代）方式实现的归并排序，再来分析一波，这种方式更加直观（为什么不直接通过非递归的方式描述，而是先通过递归的方式分析，是因为上面的过程也可以用来分析快速排序）。下面是通过非递归方式实现的归并排序代码，其中有两处分析时间复杂度的关键点，我标注出来了（重点关注注释）：