12 基本排序算法：归并排序

该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解， 而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。 时间复杂度是 O(nlogn)，空间复杂度O(n)。

归并排序就是利用归并过程，开始时先将k个数据看成k个长度为1的已排好序的表，将相邻的表成对合并，得到长度为2的（k/2）个有序表，每个表含有2个数据；进一步再将相邻表成对合并，得到长度为4的（k/4）个有序表……如此重复做下去，直到将所有数据均合并到一个长度为k的有序表为止，就完成了排序。下图显示了二路归并排序的过程。

假设使用函数merge()将两个有序表进行归并处理，并假设将两个待归并的表分别保存在数组A和B中，将其中一个表的数据安排在下标从m到n的单元中，另一个安排在下标从n+1到h的单元中，将归并后得到的有序表存入辅助数组C中。归并过程是依次比较这两个有序表中相应的数据，按照“取小”原则复制到C中。

上面函数merge()的功能只是归并两个有序表。在进行二路归并的每一趟归并过程中，能够将多对相邻的表进行归并处理。接下来开始讨论第一趟归并，假设已经将数组r中的n个数据分成成对长度为s的有序表，要求将这些表两两归并，归并成一些长度为2s的有序表，并把结果置入辅助数组r2中。如果n不是2s的整数倍，则虽然前面进行归并的表长度均为s，但是最后还是能再剩下一对长度都是s的表。 在这个时候，需要考虑如下两种情况： （1）剩下一个长度为s的表和一个长度小于s的表，由于上述归并函数merge并不要求待归并的两个表必须长度相同，所以仍可将二者归并，只是归并后的表的长度小于其他表的长度2s。 （2）只剩下一个表，它的长度小于或等于s，由于没有另一个表与它归并，所以只能将它直接复制到数组r2中，准备参加下一趟的归并。

• 平均时间复杂度：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++
		}
	}
}