归并排序的时间复杂度O(n log n)
稳定排序

样例

package main

import (
    "fmt"
    "sort"
)



func mergeSort(p []int, l, r int) {
    if l >= r {
        return
    }
    //
    mid := (r + l) >> 1
    //递归
    mergeSort(p, l, mid)
    mergeSort(p, mid+1, r)
    //合并
    i, j := l, mid+1 //指针
    //开辟一个新的数组存放
    var tmp []int
    //k := 0
    for i <= mid && j <= r {

        if p[i] <= p[j] {
            tmp = append(tmp, p[i])
            i++

        }else {
            tmp = append(tmp, p[j])
            j++

        }
        //k++
    }
    for i<=mid{
        tmp =append(tmp,p[i])
        i++
    }
    for j<=r{
        tmp =append(tmp,p[j])
        j++
    }
    //
    //p = tmp
    i,j=l,0 //
    for i<=r{
        p[i]=tmp[j]
        i++
        j++
    }
}
func main() {
    var n int
    fmt.Scanf("%d", &n)
    p := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Scanf("%d", &p[i])
    }
    //p:=[]int{3,2,1,5,4}
    //n:=5
    //mergeSort(p, 0, n-1)
    sort.Ints(p)
    for i:=0;i<n;i++{
        fmt.Printf("%d ",p[i])
    }
}