go-merge-sort

main.go

// Recursive merge sort O(n.log(n))
package main

import "fmt"

func main() {
	a := []int{9, 3, 4, 8, 4, 5, 1, 2, 6, 7, 0, 4}
	fmt.Printf("%v sorted is %v\n", a, sort(a))
}

func sort(a []int) []int {
	if len(a) <= 1 {
		return a
	}
	n := len(a) / 2
	return merge(sort(a[:n]), sort(a[n:]))
}

func merge(a []int, b []int) []int {
	c := make([]int, 0, len(a)+len(b))
	for {
		if len(a) > 0 && (len(b) == 0 || a[0] <= b[0]) {
			c, a = append(c, a[0]), a[1:]
		} else if len(b) > 0 {
			c, b = append(c, b[0]), b[1:]
		} else {
			return c
		}
	}
}