归并排序（Merge Sort）
归并排序是创立在归并操作上的一种无效的排序算法,1945年由约翰·冯·诺伊曼首次提出.该算法是采纳分治法（Divide and Conquer）的一个十分典型的利用，且各层分治递归能够同时进行。 -- 维基百科
归并排序算法采纳分治思维+递归实现：
归并排序是一种非常高效的稳固排序，每次合并操作的均匀工夫复杂度为O(n)，总的均匀工夫复杂度为O(nlogn)。
goloang code:
package mainimport ( "fmt" _ "os")func main() { var arr = [9] int {9, 8, 7, 6, 5, 4, 3, 2, 1} mergeSort(&arr) fmt.Println(arr)}func mergeSort(arr *[9]int) { var temp = [len(arr)] int {} sort(arr, 0, len(arr) - 1, &temp)}func sort(arr *[9]int, left int, right int, temp *[9] int) { if left < right { mid := (left + right) / 2 sort(arr, left, mid, temp) sort(arr, mid + 1, right, temp) merge(arr, left, mid, right, temp) }}func merge(arr *[9]int, left int, mid int, right int, temp *[9] int) { fmt.Println(left, mid, right) //os.Exit(1) i := left j := mid + 1 t := 0 for i <= mid && j <= right { if arr[i] <= arr[j] { temp[t] = arr[i] t++ i++ } else { temp[t] = arr[j] t++ j++ } } for i <= mid { temp[t] = arr[i] t++ i++ } for j <= right { temp[t] = arr[j] t++ j++ } t = 0 for left <= right { arr[left] = temp[t] left++ t++ }}