归并排序

排序简介

归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

先把n个元素分成n/2个元素的子序列，一直分到元素最小的序列；
然后分别对最小子序列排序，再把子序列合并排序。

图解参考https://www.cnblogs.com/chengxiao/p/6194356.html

复杂度

• 最佳情况：T(n) = O(nlogn)
• 最坏情况：T(n) = O(nlogn)
• 平均情况：T(n) = O(nlogn)
• 空间复杂度：O(n)
• 稳定性：稳定
• 排序方式：Out-place

golang实现

package main

import "fmt"

// 归并排序
func MergeSort(arr []int, a, b int)  {
    if b-a <= 1 {
        return
    }

    c := (a + b)/2
    MergeSort(arr, a, c)
    MergeSort(arr, c, b)
    arrLeft := make([]int, c-a)
    arrRight := make([]int, b-c)
    copy(arrLeft,arr[a:c])
    copy(arrRight, arr[c:b])
    i := 0
    j := 0
    for k := a; k < b; k++ {
        if i >= c-a { //超过数组一半
            arr[k] = arrRight[j]
            j++
        } else if j >= b-c {
            arr[k] = arrLeft[i]
            i++
        } else if arrLeft[i] < arrRight[j] {
            arr[k] = arrLeft[i]
            i++
        } else {
            arr[k] = arrRight[j]
            j++
        }
    }
}

func main()  {
    arr := []int{33,11,55,7,44,1}
    MergeSort(arr, 0, len(arr))
    fmt.Println(arr)
}