归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。
归并排序是用分治思想，分治模式在每一层递归上有三个步骤：
- 分解（Divide）：将n个元素分成个含n/2个元素的子序列。
- 解决（Conquer）：用合并排序法对两个子序列递归的排序。
- 合并（Combine）：合并两个已排序的子序列已得到排序结果。
该算法需要先将数组分解,直到每个子序列为一个元素,再将子序列两两合并排序,思路可以参考二叉树的后序递归
平均时间复杂度：O(nlogn)
最佳时间复杂度：O(n)
最差时间复杂度：O(nlogn)
空间复杂度：O(n)
速度仅次于快速排序。
稳定排序
归并排序的递归实现是先将数组分解,直到每个子序列只有一个元素,在将子序列两两归并,非递归的实现思路则没有了分解的过程,直接将数组元素一个与一个归并,在两个与两个归并,在四个与四个归并.......,直到最后两组归并,数组变为有序数组
1.⚡归并过程
gap初始化为1,每归并完一轮,gap×2(一一归并,二二归并,四四归并.........)
当gap=1,让下标为0和1的两组归并为一组,让下表为2和3的两组归并为一组..........
当gap=2,让下标为0 1和2 3的两组归并为一组,让下表为4 5和6 7的两组归并为一 组..........
当gap等于2的i次方,数组被分为两组,这两组归并完数组就排序好了
注意当每一轮归并中的每两组归并完后,要归并下两组,i要加2×gap,因为每一小组元素为 gap个
2.⚡边界控制
由于gap一直为2^i次方,所以当待排序数组的元素个数不为2^i次方时,我们默认设置的end1或begin2或end2可能会越界,所以每次进行归并时需要对他们进行控制
- 当end1越界时,说明和第一组归并的第二组就没有元素,就不需要归并操作,虽然end1越界了,但是第一组本身就是有序的,直接break跳出循环即可
- 当begin2越界时,说明和第一组归并的第二组就没有元素,就不需要归并操作,直接break跳出循环即可
- 当end2越界时,由于由于我们直到待排序数组的个数,自然知道end2的下标应该为n-1