leetcode-go/oj/algorithms/mergesort/mergesort.go

package main

import (
	"fmt"
	"math/rand"
	"time"
)

type ints []int

func (is ints) merge(aux []int, lo, mid, hi int) {
	for i, j, k := lo, mid+1, lo; k <= hi; k++ {
		if mid < i {
			aux[k] = is[j]
			j++
		} else if hi < j {
			aux[k] = is[i]
			i++
		} else if is[i] < is[j] {
			aux[k] = is[i]
			i++
		} else {
			aux[k] = is[j]
			j++
		}
	}
	copy(is[lo:hi+1], aux[lo:hi+1])
}

func (is ints) msort(aux []int, lo, hi int) {
	if hi <= lo {
		return
	}
	mid := lo + (hi-lo)/2
	is.msort(aux, lo, mid)
	is.msort(aux, mid+1, hi)
	is.merge(aux, lo, mid, hi)
}

func (is ints) sort() {
	l := len(is)
	aux := make([]int, l)
	is.msort(aux, 0, l-1)
}

func main() {
	var n int
	fmt.Scan(&n)
	var list ints = make([]int, n)
	rand.Seed(time.Now().Unix())
	for i := range list {
		list[i] = rand.Intn(2 * n)
	}
	fmt.Println(list)
	list.sort()
	fmt.Println(list)
}