package main

import "fmt"

func msort(arg []int) []int {
    if len(arg) <= 1 {
        return arg
    }

    mid := len(arg) / 2
    left := arg[:mid]
    right := arg[mid:]

    fmt.Println("split:", arg, "->", left, right)
    return merge(msort(left), msort(right))
}

func merge(left, right []int) []int {
    result := []int{}
    i, j := 0, 0

    for i < len(left) && j < len(right){
        if left[i] < right[j] {
            result = append(result, left[i])
            i += 1
        } else {
            result = append(result, right[j])
            j += 1
        }
    }

    for i < len(left) {
        result = append(result, left[i])
        i += 1
    }

    for j < len(right) {
        result = append(result, right[j])
        j += 1
    }

    fmt.Println("merge:", left, right, "->", result)
    return result
}

func main() {
    s := []int{4,2,5,1,3}
    fmt.Println(s)
    fmt.Println(msort(s))
}