12 基本排序算法：归并排序
归并排序
原理
归并排序思想
该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，
而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
时间复杂度是 O(nlogn)，空间复杂度O(n)。
归并排序就是利用归并过程，开始时先将k个数据看成k个长度为1的已排好序的表，将相邻的表成对合并，得到长度为2的（k/2）个有序表，每个表含有2个数据；进一步再将相邻表成对合并，得到长度为4的（k/4）个有序表……如此重复做下去，直到将所有数据均合并到一个长度为k的有序表为止，就完成了排序。下图显示了二路归并排序的过程。
二路归并排序过程.png
假设使用函数merge()将两个有序表进行归并处理，并假设将两个待归并的表分别保存在数组A和B中，将其中一个表的数据安排在下标从m到n的单元中，另一个安排在下标从n+1到h的单元中，将归并后得到的有序表存入辅助数组C中。归并过程是依次比较这两个有序表中相应的数据，按照“取小”原则复制到C中。
两个有序表的归并图.png
上面函数merge()的功能只是归并两个有序表。在进行二路归并的每一趟归并过程中，能够将多对相邻的表进行归并处理。接下来开始讨论第一趟归并，假设已经将数组r中的n个数据分成成对长度为s的有序表，要求将这些表两两归并，归并成一些长度为2s的有序表，并把结果置入辅助数组r2中。如果n不是2s的整数倍，则虽然前面进行归并的表长度均为s，但是最后还是能再剩下一对长度都是s的表。
在这个时候，需要考虑如下两种情况：
（1）剩下一个长度为s的表和一个长度小于s的表，由于上述归并函数merge并不要求待归并的两个表必须长度相同，所以仍可将二者归并，只是归并后的表的长度小于其他表的长度2s。
（2）只剩下一个表，它的长度小于或等于s，由于没有另一个表与它归并，所以只能将它直接复制到数组r2中，准备参加下一趟的归并。
动画演示过程
归并排序.gif
Go语言描述
- 平均时间复杂度：O(nlogn)
- 最坏时间复杂度：O(nlogn)
- 最好时间复杂度：O(nlogn)
- 空间复杂度：O(n)
- 稳定性：稳定
package sort
func MergeSort(list []int) {
l := len(list)
// 开始递归归并排序
mergeSort(list, 0, l-1)
}
// 递归：先分割后合并
func mergeSort(srcList []int, start, end int) {
// 回归条件
if start >= end {
return
}
// 获取中间索引
mid := (start + end) / 2
// 左半部分递归分割
mergeSort(srcList, start, mid)
// 右半部分递归分割
mergeSort(srcList, mid+1, end)
// 合并排序
merge(srcList, start, end, mid)
}
// 合并 以mid为中间节点的两部分数据，mid为左半部分的终点，mid+1为右半部分的起点
func merge(srcList []int, start, end, mid int) {
// 因为需要直接修改 srcList 数据，这里首先复制 [start,end] 的数据到临时数组中，用于赋值操作，每合并一次需要开辟一次空间
temp := make([]int, end-start+1)
for i := start; i <= end; i++ {
temp[i-start] = srcList[i]
}
// 指向两部分起点
left := start
right := mid + 1
for i := start; i <= end; i++ {
// 左边的点超过中点，说明只剩右边的数据
if left > mid {
srcList[i] = temp[right-start]
right++
// 右边的数据超过终点，说明只剩左边的数据
} else if right > end {
srcList[i] = temp[left-start]
left++
// 左边的数据大于右边的数据，选小的数字
} else if temp[left-start] > temp[right-start] {
srcList[i] = temp[right-start]
right++
} else {
srcList[i] = temp[left-start]
left++
}
}
}
