归并排序
作者：柳行刚
编辑：徐 松
我们是谁？
燕哥带你学算法！
我们要干什么？
学算法！
什么时候学？
天天学！
归并排序是建立在二路归并和分治法的基础上的一个高效排序算法,将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
将待排序序列R[0...n-1]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列
再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。
我们总结一下归并排序其实就只有两步：
分解:将有序序列不断地分裂，直到每个区间都只有一个数据为止。
合并:将两个区间合并为一个有序区间，一直合并直到只有一个区间为止。
其实分解的过程我们很容易想明白的，用递归就可以。但是我们今天最主要的步骤是合并，你要将两个区间合并为一个有序的区间你会怎么思考呢？
这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。
其实我们发现这种做法效率其实还是蛮高的，效率达到了O（N）.现在我们解决了合并的问题。
现在总的来看一下归并排序的做法,通过先递归的分解数列(将数列分解成只有一个元素的区间)，再合并数列就完成了归并排序。
归并排序的效率是比较高的，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(N*logN)。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在O(N*logN)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。
| 算法名称 | 最差时间复杂度 | 平均时间复杂度 | 最优时间复杂度 | 空间复杂度 | 稳定性 |
归并排序 | O(NlogN) | O(NlogN) | O(NlogN) | O(n) | 稳定 |
堆排序，快速排序，归并排序.
若从空间复杂度来考虑：
首选堆排序，其次是快速排序，最后是归并排序。
若从稳定性来考虑：
应选取归并排序，因为堆排序和快速排序都是不稳定的。
若从平均情况下的排序速度考虑：
应该选择快速排序。
理解了归并排序算法了吗？
若还有疑问，欢迎在留言板处提问哦！
1
推荐阅读
你知道如何求集合全排列和所有子集么？
快扫描下方二维码，听听本文原作者柳行刚的深度分析吧~
点个赞呗，么么哒~