Insertion sort

This sorting algorithm works very much like sorting a hand of playing cards. You start by evaluating the second leftmost card in your hand and you compare it to the one on its left. If it has a smaller value than it, then you swap them. If not, you do nothing and move on to the third card. If its value is smaller than the second card, you then also have to look at the first card because it can be even smaller. However, if it is larger than the second card, you already know that it is also larger than first and you are free to move on to the fourth card. This goes on until you’ve went through all the cards in your hand.

Now that we have the reasoning behind it chalked down, we can introduce some formal language. This is an algorithm to solve the sorting problem, where we are given a sequence of $n$ numbers, $\langle a_1, a_2, …, a_n \rangle$, as input and we want to produce an output which is a permutation of the input sequence, $\langle a_1’, a_2’, …, a_n’ \rangle$, such that $a_1’ \leq a_2’ \leq … \leq a_n’$. In practice, our input comes in the form of an array, $A[1 .. n]$, containing a sequence of length $n$, and we will sort the number in place, meaning that they will be rearranged within the array, in other words, the output array is the input array after having gone through the algorithm. This algorithm has a worst-case (and average-case) time complexity of $O(n^2)$, and a best case scenario time complexity of $O(n)$, which happens when the input array is almost sorted.

Pseudocode

We can describe the algorithm in pseudocode (assuming array indexes start in 1) as follows:

1
2
3
4
5
6
7
8
9

INSERTION-SORT(A)

for j = 2 to A.length
    key = A[j]
    i = j - 1
    while i > 0 and A[i] > key
        A[i+1] = A[i]
        i = i - 1
    A[i+1] = key

Implementation

Implementing this algorithm from pseudocode is incredibly straightforward. Below are some implementation examples in Go, Ruby, Python and Rust.

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def insertion_sort(array):
    for j in range(1, len(array)):
        key = array[j]
        i = j - 1
        while i >= 0 and array[i] > key:
            array[i+1] = array[i]
            i = i - 1
        array[i+1] = key

array = [43, 2, 21, 3, 70, 8]
insertion_sort(array)
print(array)

Go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

package main

import "fmt"

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

func main() {
	array := []int{43, 2, 21, 3, 70, 8}
	insertionSort(array)
	fmt.Println(array)
}

Rust

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

fn insertion_sort(array: &mut [i32]) {
    for j in 1..array.len() {
        let mut i = j;
        let key = array[j];

        while i > 0 && key < array[i - 1] {
            array[i] = array[i - 1];
            i -= 1;
        }

        array[i] = key;
    }
}

fn main() {
    let mut array: [i32; 6] = [43, 2, 21, 3, 70, 8];
    insertion_sort(&mut array);
    println!("{:?}", array);
}

References

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 3rd Edition