Go语言归并排序算法

mergesort.go

package main

import "log"

func MergeSort(a []int) []int {
	l := len(a)
	if l <= 1 {
		return a
	}

	// split
	left := MergeSort(a[:l/2])
	right := MergeSort(a[l/2:])

	// merge
	result := make([]int, l)
	var lIndex, rIndex int
	for i := 0; i < l; i++ {
		switch {
		case rIndex >= len(right): // right is empty
			result[i] = left[lIndex]
			lIndex++
		case lIndex >= len(left): // left is empty
			result[i] = right[rIndex]
			rIndex++
		case left[lIndex] < right[rIndex]: // head element left < right
			result[i] = left[lIndex]
			lIndex++
		default: // else
			result[i] = right[rIndex]
			rIndex++
		}
	}
	return result
}

func main() {
	log.Println(MergeSort([]int{}))
	log.Println(MergeSort([]int{6}))
	log.Println(MergeSort([]int{1, 2}))
	log.Println(MergeSort([]int{5, 2}))
	log.Println(MergeSort([]int{6, 4, 3, 2, 1, 5}))
	log.Println(MergeSort([]int{5, 2, 0, 1, 3, 1, 4}))
}

输出信息：

2019/06/28 22:22:49 []
2019/06/28 22:22:49 [6]
2019/06/28 22:22:49 [1 2]
2019/06/28 22:22:49 [2 5]
2019/06/28 22:22:49 [1 2 3 4 5 6]
2019/06/28 22:22:49 [0 1 1 2 3 4 5]