归并排序

package main

import (
    "bufio"
    "encoding/json"
    "fmt"
    "os"
    "strconv"
)
func main() {
    var input []int
    reader := bufio.NewReader(os.Stdin)
    s, err := reader.ReadString('\n')
    if err != nil {
        fmt.Println("err:", err)
    }
    err = json.Unmarshal([]byte(s), &input)
    if err != nil {
        fmt.Println("err:", err)
    }
    sort(input, 0, len(input))
    res := "["
    for i, v := range input {
        res += strconv.Itoa(v)
        if i != len(input) - 1 {
            res += ", "
        }
    }
    res += "]"
    fmt.Println(res)
}

func sort(arr []int, l, r int) {
    if l == r - 1 {
        return
    }
    mid := l + (r - l) >> 1
    sort(arr, l, mid)
    sort(arr, mid, r)
    p, q, i := l, mid, 0
    tmp := make([]int, r - l)
    for p < mid && q < r {
        if arr[p] < arr[q] {
            tmp[i] = arr[p]
            p++
        } else {
            tmp[i] = arr[q]
            q++
        }
        i++
    }
    for p < mid {
        tmp[i] = arr[p]
        i, p = i + 1, p + 1
    }
    for q < r {
        tmp[i] = arr[q]
        i, q = i + 1, q + 1
    }
    for j := l; j < r; j++ {
        arr[j] = tmp[j - l]
    }
}