A merge sort algorithm implementation in Go.

merge_sort.go

package main

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

func merge(xs, ys []int) []int {
	sizex, sizey := len(xs), len(ys)
	zs := []int{}

	i, j := 0, 0
	for i < sizex && j < sizey {
		if xs[i] < ys[j] {
			zs = append(zs, xs[i])
			i++
		} else {
			zs = append(zs, ys[j])
			j++
		}
	}

	// append rest elements
	// i >= len(arr) => arr[i:] == []
	zs = append(zs, xs[i:]...)
	zs = append(zs, ys[j:]...)
	return zs
}

func MergeSort(arr []int) []int {
	size := len(arr)
	if size <= 1 {
		return arr
	}

	xs := MergeSort(arr[:size/2])
	ys := MergeSort(arr[size/2:])
	return merge(xs, ys)
}

func main() {
	for i := 0; i < 100; i++ {
		// run test with random inputs
		rand.Seed(time.Now().UnixNano())
		input := rand.Perm(100)
		sorted := MergeSort(input)
		if len(sorted) != len(input) || !sort.IsSorted(sort.IntSlice(sorted)) {
			panic(sorted)
		}
	}
}