归并排序

参考：https://zhuanlan.zhihu.com/p/124356219

时间复杂度：O(nlogn)
空间复杂度：O(n)
稳定性：稳定

func mergeSort(arr []int) {
	temp := make([]int, len(arr))
	mergeRecursive(arr, temp, 0, len(arr) - 1)
}

//归并排序
func mergeRecursive(arr []int, result []int, start, end int) {
	if start >= end {
		return
	}
	end1 := (end-start)>>1 + start
	start1, start2 := start, end1 + 1
	mergeRecursive(arr, result, start1, end1)
	mergeRecursive(arr, result, start2, end)
	k := start
	for ; start1 <= end1 && start2 <= end; {
		if arr[start1] < arr[start2] {
			result[k] = arr[start1]
			start1++
		} else {
			result[k] = arr[start2]
			start2++
		}
		k++
	}
	for ; start1 <= end1; {
		result[k] = arr[start1]
		start1++
		k++
	}
	for ; start2 <= end; {
		result[k] = arr[start2]
		start2++
		k++
	}
	for k = start; k <= end; k++ {
		arr[k] = result[k]
	}
}