归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

MergeSort.go

func Sort[T constraints.Ordered](buf []T) {
    tmp := make([]T, len(buf))
    merge_sort[T](buf, 0, len(buf)-1, tmp)
}

func merge_sort[T constraints.Ordered](a []T, first, last int, tmp []T) {
    if first < last {
        middle := (first + last) / 2
        merge_sort(a, first, middle, tmp)       //左半部分排好序
        merge_sort(a, middle+1, last, tmp)      //右半部分排好序
        mergeArray[T](a, first, middle, last, tmp) //合并左右部分
    }
}

func mergeArray[T constraints.Ordered](a []T, first, middle, end int, tmp []T) {
    i, m, j, n, k := first, middle, middle+1, end, 0
    for i <= m && j <= n {
        if a[i] <= a[j] {
            tmp[k] = a[i]
            k++
            i++
        } else {
            tmp[k] = a[j]
            k++
            j++
        }
    }
    for i <= m {
        tmp[k] = a[i]
        k++
        i++
    }
    for j <= n {
        tmp[k] = a[j]
        k++
        j++
    }

    for ii := 0; ii < k; ii++ {
        a[first+ii] = tmp[ii]
    }
}