关于数据结构和算法:常用排序算法之归并排序

归并排序（Merge Sort）

归并排序是创立在归并操作上的一种无效的排序算法,1945年由约翰·冯·诺伊曼首次提出.该算法是采纳分治法（Divide and Conquer）的一个十分典型的利用，且各层分治递归能够同时进行。 — 维基百科

归并排序算法采纳分治思维+递归实现：

归并排序是一种非常高效的稳固排序，每次合并操作的均匀工夫复杂度为O(n)，总的均匀工夫复杂度为O(nlogn)。

goloang code:

package main

import (
    "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++
    }

}