GO语言归并排序

归并排序 归并排序（Merge sort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用

func mergeSort(items []int) []int {
    var n = len(items)
    if n == 1 {
        return items
    }
    middle := int(n / 2)
    var (
        left  = make([]int, middle)
        right = make([]int, n-middle)
    )
    for i := 0; i < n; i++ {
        if i < middle {
            left[i] = items[i]
        } else {
            right[i-middle] = items[i]
        }
    }
    return merge(mergeSort(left), mergeSort(right))
}
func merge(left, right []int) (result []int) {
    result = make([]int, len(left)+len(right))
    i := 0
    for len(left) > 0 && len(right) > 0 {
        if left[0] < right[0] {
            result[i] = left[0]
            left = left[1:]
        } else {
            result[i] = right[0]
            right = right[1:]
        }
        i++
    }
    // Either left or right may have elements left; consume them.
    // (Only one of the following loops will actually be entered.)
    for j := 0; j < len(left); j++ {
        result[i] = left[j]
        i++
    }
    for j := 0; j < len(right); j++ {
        result[i] = right[j]
        i++
    }
    return
}