归并排序 - Mohuishou

注：本文已发布超过一年，请注意您所使用工具的相关版本是否适用

说明

归并排序:是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用

步骤

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤 3 直到某一指针达到序列尾
将另一序列剩下的所有元素直接复制到合并序列尾

示例

package merge

//INFINITY 一个比较大的值用作哨兵
const INFINITY = 0xffff

func merge(arr []int, start, end int) {
	if start < end {
		//从中间划分，分别左右两边排序
		mid := (end + start) / 2
		merge(arr, start, mid)
		merge(arr, mid+1, end)

		//下面进行归并操作，将两个长度较小但是已经排序完成的数组合并成一个较长长度的排序数组

		//新建一个数组用于存放左边的值
		arr1 := make([]int, mid-start+2)
		copy(arr1, arr[start:mid+1])
		arr1[mid-start+1] = INFINITY

		//新建一个数组用于存放右边的值
		arr2 := make([]int, end-mid+1)
		copy(arr2, arr[mid+1:end+1])
		arr2[end-mid] = INFINITY

		//比较大小
		j, k := 0, 0
		for i := start; i <= end; i++ {
			if arr1[j] <= arr2[k] {
				arr[i] = arr1[j]
				j++
			} else {
				arr[i] = arr2[k]
				k++
			}
		}

	}
}