题解 | #排序#

package main

func MySort(arr []int) []int {
	// write code here
	le := len(arr)
	tmp := make([]int, le, le)
	doSort(arr, tmp, 0, le-1)
	return arr
}

func doSort(arr []int, tmp []int, st int, en int) {
	//fmt.Println(st)
	//fmt.Println(en)
	if st >= en {
		return
	}
	mid := (st + en) / 2
	doSort(arr, tmp, st, mid)
	doSort(arr, tmp, mid+1, en)

	for i, j, k := st, mid+1, st; i <= mid || j <= en; {
		if i > mid || (j <= en && arr[i] > arr[j]) {
			tmp[k] = arr[j]
			j++
			k++
			continue
		}
		if j > en || (i <= mid && arr[i] <= arr[j]) {
			tmp[k] = arr[i]
			i++
			k++
		}
	}

	for i := st; i <= en; i++ {
		arr[i] = tmp[i]
	}

}