归并排序比较占用内存，但却是一种效率高且稳定的算法。
 改进归并排序在归并时先判断前段序列的最大值与后段序列最小值的关系再确定是否进行复制比较。如果前段序列的最大值小于等于后段序列最小值，则说明序列可以直接形成一段有序序列不需要再归并，反之则需要。所以在序列本身有序的情况下时间复杂度可以降至O(n)
 TimSort可以说是归并排序的终极优化版本，主要思想就是检测序列中的天然有序子段（若检测到严格降序子段则翻转序列为升序子段）。在最好情况下无论升序还是降序都可以使时间复杂度降至为O(n)，具有很强的自适应性。

归并排序方法就是把一组n个数的序列，折半分为两个序列，然后再将这两个序列再分，一直分下去，直到分为n个长度为1的序列。然后两两按大小归并。如此反复，直到最后形成包含n个数的一个数组。
 
归并排序总时间=分解时间+子序列排好序时间+合并时间
 
无论每个序列有多少数都是折中分解，所以分解时间是个常数，可以忽略不计。
 
则：归并排序总时间=子序列排好序时间+合并时间
 

如果假设一个序列有n个数的排序时间为T(n)，T(n)是一个关于n的函数，随着n的变化而变化。
 
那么我们将n个数的序列，分为两个(n/2)的序列。
 
 
那么T(n)=2*T(n/2)+合并时间
 
由于合并时，两个子序列已经组内排好序了，那我们将两个排好序的序列组合成一个大的有序序列，只需要一个if循环即可。if循环中有n个数需要比较，所以时间复杂度为n。
 
那么T(n)=2*T(n/2)+n
 
 
 
我们再将两个n/2个序列再分成4个(n/4)的序列。
 
 
一个（n/2）序列排序时间=两个(n/4)的序列排序时间+两个(n/4)的序列的合并为一个（n/2）的序列时间
 
T(n/2)=2*T(n/4)+n/2
 
将T(n/2)带入到T(n)中，T(n)=2*(2*T(n/4)+n/2)+n，
 
通过化简T(n)=4*T(n/4)+2n
 
 
 
我们再将4个n/4个序列再分成8个(n/8)的序列。
 
 
T(n/4)=2*T(n/8)+n/4
 
将T(n/4)带入到黄色公式中，T(n)=4*(2*T(n/8)+n/4)+2n
 
通过化简T(n)=8*T(n/8)+3n
 
······
 

这样分下去，前面我们已经说过了，分为n个序列，每个序列里只有一个数为止。
 
前面我们假设的一个序列有n个数的排序时间为T(n)，现在每个序列只有一个数，所以不需要进行组内排序，时间复杂度为0。T(1)=0
 
 
大家有没有找到规律，右边式子中n前面的系数随着层数的增加而增加，第一层公式中没有n，则系数为0，第二层n的系数为1，第三层为2，第四层为3。那么规律就出来了，n前面的系数为层数减1。
 
那这个图有没有很熟悉，就像一个二叉树一样，通过二叉树的知识点我们可以知道，一个n个结点的二叉树层数为(log2n)+1。
 
那么n前面的系数为层数减1。
 
(log2n)+1-1=log2n
 
那log2n就是最底层n的系数。
 
 
 
那么我们最后一层是不是可以这样表示
 
T(n)=n*T(1)+(log2n)*n
 
T(1)=0，那么T(n)=(log2n)*n
 
所以归并排序的时间复杂度为nlog2n

归并排序算法你还记得吧？它的递归实现代码非常简洁。现在我们就借助归并排序来看看，如何用递归树，来分析递归代码的时间复杂度。
 
归并排序每次会将数据规模一分为二。我们把归并排序画成递归树，就是下面这个样子：
 
 因为每次分解都是一分为二，所以代价很低，我们把时间上的消耗记作常量 1。归并算法中比较耗时的是归并操作，也就是把两个子数组合并为大数组。从图中我们可以看出，每一层归并操作消耗的时间总和是一样的，跟要排序的数据规模有关。我们把每一层归并操作消耗的时间记作 n。
 
现在，我们只需要知道这棵树的高度 h，用高度 h 乘以每一层的时间消耗 n，就可以得到总的时间复杂度 O(n∗h)。
 
从归并排序的原理和递归树，可以看出来，归并排序递归树是一棵满二叉树。我们前两节中讲到，满二叉树的高度大约是 log2​n，所以，归并排序递归实现的时间复杂度就是 O(nlogn)。我这里的时间复杂度都是估算的，对树的高度的计算也没有那么精确，但是这并不影响复杂度的计算结果。
 
总结
 
归并排序的时间复杂读为nlogn,每一行时间复杂度O(n) 然后二叉树高度log(n)
 
参考
 
归并排序图解_鸭梨的博客-CSDN博客
 

来自教程：https://time.geekbang.org/column/article/41913
 
我们对n个元素进行归并排序，需要时间T(n)，
 
那分解成两个子数组排序的时间都是T(n/2)。
 
merge()函数合并的时间复杂度是O(n)。
 
归并排序的时间复杂度计算公式是：
 
T(1) = C；   n=1 时，只需要常量级的执行时间，所以表示为 C。
T(n) = 2*T(n/2) + n； n>1
 
如何求T(n)？
 
我们对T(n/2)一级一级分解：
 
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
     ......
 
可以看出：
 
当时，就是最底层，也就是进行了k次之后达到了最底层。
 
求出，带入T(n)的公式，求出：，使用大O表示法：T(n) = O(nlogn);
 
而且归并排序的算法跟有序度无关，所以时间复杂度很稳定都是O(nLogN)；