【CPP】归并排序

1.归并排序

归并排序（MERGE-SORT） 是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并分割的意义：把整个数组分割为以个为单位。

简介

代码

分析

时间复杂度：O(N*logN)
空间复杂度：O(N)

归并的非递归形式

归并非递归形式可以用栈吗？
**不适合用栈。**原因在于快排用栈本质上是因为快排是一种前序遍历，遍历完之后就不需要再管原来的区间了，但是归并是先分而后并，是一种后序遍历， 栈很难控制，问题在于递归之后回不去了。

那如何解决？直接省略递归分割过程，直接去模拟回归的过程。

我们发现：
归并是消耗空间复杂度O(N)的，由于归并的这一特性可以做外排序(外排序就是在内存外即硬盘中进行排序)。

EOF