Merge Sort

mergesort.go

package main

import "fmt"

// mergeSort splits an array into sub arrays until they are of length 1. A
// length 1 array is sorted. Then the sorted arrays are merged
func mergeSort(arr []int) []int {
	// If an array has a length of one then it is sorted
	length := len(arr)
	if length <= 1 {
		return arr
	}
	// Break array into sub arrays
	mid := length /2
	arr1 := mergeSort(arr[:mid])
	arr2 := mergeSort(arr[mid:])

	// Merge arrays
	return merge(arr1, arr2)
}

// merge joins two sorted arrays
func merge(arr1, arr2 []int) []int {
	// Initialize a sorted array
	var sorted []int

	// Iterate through the two sorted arrays adding the smaller elements to the
	// sorted array and removing the element from the sub array
	for 0 < len(arr1) && 0 < len(arr2) {
		if arr1[0] < arr2[0] {
			sorted = append(sorted, arr1[0])
			arr1 = arr1[1:]
		} else {
			sorted = append(sorted, arr2[0])
			arr2 = arr2[1:]
		}
	}

	// Add any remaining elements to the sorted array. At this point one of the
	// arrays was fully iterated through so only one of the following lines will
	// be adding elements to the sorted array
	sorted = append(sorted, arr1...)
	sorted = append(sorted, arr2...)

	// Return sorted array
	return sorted
}

func main() {
	array := []int{4, 3, 5, 6, 8, 2, 1, 7}
	fmt.Println(mergeSort(array))
}