合并排序

合并排序是基于分治思想的：
1. 如果数组足够小，直接对数组进行排序。
2. 否则，把数组划分为两个子数组，分别进行合并排序，然后合并两个有序的子数组为有序数组。

进行合并操作的复杂度为O(n)，由于每次把数组分为2个子数组，需要进行lg(n)次合并，所以时间复杂度为O(n*lg(n))，。

每次合并都需要与两个子数组长度和 大小的数组，所以空间复杂度为O(n)。

实现

func MergeSort(arr []int) []int {
    length := len(arr)
    if length < 2 {
        return arr
    }

    mid := length >> 1
    //mid := length / 2
    larr := MergeSort(arr[0:mid])
    rarr := MergeSort(arr[mid:length])

    return merge(larr, rarr, asc)
}

func merge(larr []int, rarr []int, compare func(int, int) bool) []int {
    lLen, rLen := len(larr), len(rarr)
    arr := make([]int, lLen+rLen)

    l, r, i := 0, 0, 0
    for ; l < lLen && r < rLen; i++ {
        if compare(larr[l], rarr[r]) {
            arr[i] = rarr[r]
            r++
        } else {
            arr[i] = larr[l]
            l++
        }
    }

    if l >= lLen {
        util.ArrayCopy(rarr, r, arr, i, rLen-r)
    } else {
        util.ArrayCopy(larr, l, arr, i, lLen-l)
    }

    return arr
}

func asc(l int, r int) bool {
    return l > r
}

欢迎关注我的微信公众号: coderbee笔记，可以更及时回复你的讨论。