An example of the merge sort algorithm written in Go.

merge-sort-no-comments.go

package main

import "fmt"

func Split(s []int) ([]int, []int) {
	mid := len(s)/2

	a := s[:mid]
	b := s[mid:]

	return a, b
}

func Merge(a, b []int) []int {
	c := make([]int, len(a)+len(b))

	var i, j, k int

	for i < len(a) && j < len(b) {
		if a[i] < b[j] {
			c[k] = a[i]
			i++
		} else {
			c[k] = b[j]
			j++
		}
		k++
	}

	if i == len(a) {
		copy(c[k:], b[j:])
	}

	if j == len(b) {
		copy(c[k:], a[i:])
	}

	return c
}

func Sort(s []int) []int {
	if len(s) < 2 {
		return s
	}

	a, b := Split(s)

	return Merge(Sort(a), Sort(b))
}
	

func main() {
	a := []int{23,154,93,49,-23,33,2,56,-3,3,82,24,27,1,7,63,14,95}

	fmt.Println(Sort(a))
}

merge-sort.go

package main

import "fmt"

// Split takes a single slice and returns the first and second half as
// two separate slices. Given a slice of uneven length the second half
// will contain the extra element.
func Split(s []int) ([]int, []int) {

	mid := len(s)/2

	// a will contain everything up to but not including the mid
	// point of s.
	a := s[:mid]

	// b will contain the mid point and everything after of s.
	b := s[mid:]

	return a, b
}

// Merge expects two sorted slices and merges them into a single
// sorted slice. 
func Merge(a, b []int) []int {
	// slice to hold merged slices where the length is equal to
	// the sum of both slices
	c := make([]int, len(a)+len(b))

	// counters
	var i, j, k int

	// loop over both a and b without falling off either
	for i < len(a) && j < len(b) {
		// compare the i'th element of a to the j'th element
		// of b
		if a[i] < b[j] {
			// i'th element of a is smaller than j'th
			// element of b, add it to c
			c[k] = a[i]
			i++
		} else {
			// j'th element of b is smaller than i'th
			// element of a, add it to c
			c[k] = b[j]
			j++
		}
		// increment c's counter
		k++
	}

	// a is exhausted, copy rest of b into c
	if i == len(a) {
		copy(c[k:], b[j:])
	}

	// b is exhaused, copy rest of a into c
	if j == len(b) {
		copy(c[k:], a[i:])
	}

	return c
}

// Sort is a recursive function that continually splits and merges a
// slice until only one element is returned.
func Sort(s []int) []int {
	// The base case: stop sorting if only one element
	// remains. Just return the slice containing a single element.
	if len(s) < 2 {
		return s
	}

	// Split s into two separate slices, a and b.
	a, b := Split(s)


	// Recursively call Sort on both a and b while merging them on
	// each iteration.
	return Merge(Sort(a), Sort(b))
}
	

func main() {
	a := []int{23,154,93,49,-23,33,2,56,-3,3,82,24,27,1,7,63,14,95}

	fmt.Println(Sort(a))
}