Go Merge Sort

merge_sort.go

package main

import (
	"log"
)

func main() {
	array := []int{}
	assert([]int{}, mergeSort(array))

	array = []int{1}
	assert([]int{1}, mergeSort(array))

	array = []int{1, 2}
	assert([]int{1, 2}, mergeSort(array))

	array = []int{3, 1, 2}
	assert([]int{1, 2, 3}, mergeSort(array))

	array = []int{3, 2, 1, 4}
	assert([]int{1, 2, 3, 4}, mergeSort(array))
}

func mergeSort(arr []int) (sorted []int) {
	if len(arr) <= 1 {
		return arr
	}

	mid := len(arr) / 2

	return merge(mergeSort(arr[:mid]), mergeSort(arr[mid:]))
}

func merge(left, right []int) []int {
	result := make([]int, len(left)+len(right))

	i := 0
	for len(left) > 0 && len(right) > 0 {
		if left[0] > right[0] {
			result[i] = right[0]
			right = right[1:]
		} else {
			result[i] = left[0]
			left = left[1:]
		}
		i++
	}

	for len(left) > 0 {
		result[i] = left[0]
		left = left[1:]
		i++
	}
	for len(right) > 0 {
		result[i] = right[0]
		right = right[1:]
		i++
	}

	return result
}

func assert(expected, actual []int) {
	if len(expected) != len(actual) {
		log.Panicf("%s != %s", expected, actual)
	}
	for x := range expected {
		if expected[x] != actual[x] {
			log.Panicf("%s != %s", expected, actual)
		}
	}
}