Learn coding concepts by building real projects with modern technologies

How to Write Insertion Sort in Go

By Lane Wagner on Jun 14, 2021

Insertion sort builds a final sorted list one item at a time. It’s much less efficient on large lists than more advanced algorithms like quicksort or merge sort. Insertion sort is a simple algorithm that works just like you would arrange playing cards in your hands. A slice is first split into sorted and unsorted sections, then values from the unsorted section are inserted into the correct position in the sorted section.

Full example of the insertion sort algorithm

func insertionSort(arr []int) []int {
	for i := 0; i < len(arr); i++ {
		for j := i; j > 0 && arr[j-1] > arr[j]; j-- {
			arr[j], arr[j-1] = arr[j-1], arr[j]
		}
	}
	return arr
}

As you can see, the insertionSort() function starts by iterating over the entire slice in a nested for loop. The job of the inner for loop is to consume one value for each repetition, and grow the sorted output list, which are all the elements before index i. At each repetition, insertion sort removes one element from the input data, finds the location it belongs within the sorted first section, and inserts it there. It repeats until no input elements remain.

Using insertion sort in code

func main() {
    fmt.Println(insertionSort([]int{5,3,2,1,0,4))
    // prints
    // [0, 1, 2, 3, 4, 5]
}

Learn Go by writing Go code

I'm a senior engineer learning Go, and the pace of Boot.dev's Go Mastery courses has been perfect for me. The diverse community in Discord makes the weekly workshops a blast, and other members are quick to help out with detailed answers and explanations.

- Daniel Gerep from Cassia, Brasil

Why use insertion sort?

Insertion sort has a Big O complexity of O(n^2), because that is its worst-case complexity. The outer loop of insertion sort executes n times, while the inner loop depends on the input. In the worst case (a reverse sorted array) the inner loop executes n times as well. In the best case (a sorted array) the inner loop immediately breaks resulting in a total complexity of O(n).

Like bubble sort, the algorithm is just too slow for general-purpose production use, but can be a great learning tool. Here are some additional properties of insertion sort.

Some production sorting implementations use merge sort for ver small inputs under a certain threshold (a very small threshold, usually about 10 items). Insertion sort is better for very small lists than some of the faster algorithms because:

Learn to code by building real projects

Related Reading