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

归并排序（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++
    }

}