归并排序

• 算法实现

func merge(list []int, left, mid, right int) {
	lLen := mid - left + 1
	rLen := right - mid
	length := lLen + rLen
	result := make([]int, length)
	// 左边起始位置：left 右边起始位置mid + 1
	// 真实位置： 起始位置 + 索引位置
	for idx, lIdx, rIdx := 0, 0, 0; idx < length; idx++ {
		if lIdx >= lLen {
			result[idx] = list[mid+1+rIdx]
			rIdx++
		} else if rIdx >= rLen {
			result[idx] = list[left+lIdx]
			lIdx++
		} else if list[left+lIdx] > list[mid+1+rIdx] {
			result[idx] = list[mid+1+rIdx]
			rIdx++
		} else {
			result[idx] = list[left+lIdx]
			lIdx++
		}
	}
	// 写回去
	for idx := 0; idx < length; idx++ {
		list[left+idx] = result[idx]
	}
}

func MergeSort(list []int, left, right int) {
	if left < right {
		mid := (left + right) / 2
		MergeSort(list, left, mid)
		MergeSort(list, mid+1, right)
		merge(list, left, mid, right)
	}
}

• 测试代码

func main() {
	list := []int{8, 4, 8, 2, 9, 10, -3, 3, 20, 15, -1}
	function.MergeSort(list, 0, len(list)-1)
	fmt.Println(list)
}

• 排序结果

[-3 -1 2 3 4 8 8 9 10 15 20]

• 时间复杂度

O (nlogn)

• 空间复杂度

就是 n + logn，所以是线性空间复杂度

O (n)