How to Write Insertion Sort in Go
Tags: go, mailinglist
Published: 2021-06-24 02:29:24

---
title: How to Write Insertion Sort in Go
published: true
date: 2021-06-14 12:23:33 UTC
tags: Golang,mailinglist
canonical_url: https://qvault.io/golang/insertion-sort-golang/
---

 ![insert](https://qvault.io/wp-content/uploads/2021/06/insert.jpg "insert")

The post [How to Write Insertion Sort in Go](https://qvault.io/golang/insertion-sort-golang/) first appeared on [Qvault](https://qvault.io).

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](https://qvault.io/golang/merge-sort-golang/). 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.

![insertionsort](https://qvault.io/wp-content/uploads/2021/06/insertionsort.gif "insertionsort")

## Full example of the insertion sort algorithm

```go
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
}
<small id="shcb-language-1"><span>Code language:</span> <span>Go</span> <span>(</span><span>go</span><span>)</span></small>
```

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

```go
func main() {

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

<small id="shcb-language-2"><span>Code language:</span> <span>Go</span> <span>(</span><span>go</span><span>)</span></small>
```

## 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](https://qvault.io/golang/bubble-sort-golang/), 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.

- Simple implementation, easy to write
- Fast for very small data sets
- Faster than other simple sorting algorithms like Bubble Sort
- Adaptive: Faster for partially sorted data sets
- Stable: Does not change the relative order of elements with equal keys
- In-Place: Only requires a constant amount of memory
- Online: Can sort a list as it receives it

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

- There is no recursion overhead
- Tiny memory footprint
- It’s a stable sort as described above

Ready to take action and get coding?

[<svg aria-hidden="true" role="img" height="1em" width="1em" viewbox="0 0 256 512" xmlns="http://www.w3.org/2000/svg"><path fill="currentColor" d="M224.3 273l-136 136c-9.4 9.4-24.6 9.4-33.9 0l-22.6-22.6c-9.4-9.4-9.4-24.6 0-33.9l96.4-96.4-96.4-96.4c-9.4-9.4-9.4-24.6 0-33.9L54.3 103c9.4-9.4 24.6-9.4 33.9 0l136 136c9.5 9.4 9.5 24.6.1 34z"></path></svg>Try out our coding courses for free](https://app.qvault.io/)

<svg aria-hidden="true" role="img" height="1em" width="1em" viewbox="0 0 256 512" xmlns="http://www.w3.org/2000/svg"><path fill="currentColor" d="M224.3 273l-136 136c-9.4 9.4-24.6 9.4-33.9 0l-22.6-22.6c-9.4-9.4-9.4-24.6 0-33.9l96.4-96.4-96.4-96.4c-9.4-9.4-9.4-24.6 0-33.9L54.3 103c9.4-9.4 24.6-9.4 33.9 0l136 136c9.5 9.4 9.5 24.6.1 34z"></path></svg>[Join our Discord community](https://discord.com/invite/EEkFwbv)

## Have questions or feedback?

Follow and hit me up on Twitter [@q\_vault](https://twitter.com/q_vault) if you have any questions or comments. If I’ve made a mistake in the article be sure to [let me know](https://qvault.io/contact/) so I can get it corrected!