go实现归并排序

package main

import "fmt"

func main() {
	arr := []int{0, 8, 0, 10, 5, 4, 2, 0, 1, 7}
	ret := MergeSort(arr)
	fmt.Println(ret)
}

// 归并排序
func MergeSort(nums []int) []int {
	arrLen := len(nums)
	if arrLen < 2 {
		return nums
	}
	i := arrLen >> 1

	// 利用定义，排序左半部分
	left := MergeSort(nums[0:i])

	// 利用定义，排序右半部分
	right := MergeSort(nums[i:])

	/****** 后序位置 ******/
	// 此时两部分子数组已经被排好序
	// 合并两个有序数组
	return merge(left, right)
}

func merge(left []int, right []int) []int {
	m := len(left)
	n := len(right)
	result := make([]int, m+n, m+n)
	i, j, k := 0, 0, 0
	for i < m && j < n {
		if left[i] >= right[j] {
			result[k] = left[i]
			i++
		} else {
			result[k] = right[j]
			j++
		}
		k++
	}

	// 左边先完成, 右边还有剩余未合并的数据
	if i == m {
		for j < n {
			result[k] = right[j]
			k++
			j++
		}
	}

	// 右边边先完成, 左边还有剩余未合并的数据
	if j == n {
		for i < m {
			result[k] = left[i]
			k++
			i++
		}
	}

	return result
}