归并排序-golang

归并排序-golang

package main
import "fmt"

var n int
var arr []int

func main(){
    fmt.Scanf("%d", &n)

    arr = make([]int, n)

    for i := 0; i < n; i++{
        fmt.Scanf("%d", &arr[i])
    }

    mergeSort(arr, 0, n-1)

    for i := 0; i < n; i++{
        fmt.Printf("%d ", arr[i])
    }
}

func mergeSort(arr []int, start, end int){
    if start >= end{
        return 
    }

    mid := (start+end)>>1


    tmp := make([]int, 0, end-start+1)

    mergeSort(arr, start, mid)
    mergeSort(arr, mid+1, end)

    i, j := start, mid+1

    for i <=mid && j <=end{
        if arr[i] <= arr[j]{
            tmp = append(tmp, arr[i])
            i++
        }else{
            tmp = append(tmp, arr[j])
            j++
        }
    }

    for i <= mid{
        tmp = append(tmp, arr[i])
        i++
    }

    for j <= end{
        tmp = append(tmp, arr[j])
        j++
    }
    copy(arr[start:end+1], tmp)
}