Don't spend $10k on a bootcamp. Try our back-end career path first.
Back home

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]
}

A simple path to your career in back-end development

The pace of Boot.dev's JavaScript, Python and Go courses has been perfect for me. The diverse community in Discord is 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 back-end without spending $10,000+ on a bootcamp

Related Reading