Algorithms

Insertion Sort

Insertion sort builds the list in order one value at a time, sliding each new value back through the sorted part until it lands in the right spot.

Strategy

Incremental construction

Keep a sorted run at the front and grow it by one value at a time.

Take: pick up the first value sitting outside the sorted run.
Place: slide bigger values one slot right until the gap is where it belongs.
Grow: drop the value in, and the sorted run is one longer.

sorted section key / active shift not reached yet

Press Step to place one value at a time. The left side stays sorted, and each new value slides back until it finds its gap.

Purpose

Put a slice of values in order, smallest to largest.

Input

An unsorted []int.

Output

The same slice, sorted in place.

Constraints

A nearly sorted list is the fast case, since most values barely move.
Values shift one slot at a time, so a reversed list is the slow case.
Equal values keep their order, so the sort is stable.

How insertion sort works

It is how most people sort a hand of cards. You hold the sorted cards on the left, pick up the next one, and slide it back along the hand until it sits between a smaller card and a bigger one. Do that for every card and the hand is sorted.

It is quick on small lists and on lists that are nearly sorted already, which is why real sorting libraries switch to it once the pieces get small enough.

What insertion sort keeps track of

Name	Type	What it is for
a	[]int	The values you are sorting, shuffled in place.
i	int	The card you have just picked up.
v	int	A copy of that value, kept safe while slots shift.
j	int	Walks back through the sorted part looking for the gap.

Walk through it

1 Start with a slice

It is sorted where it sits, so nothing comes back.

a := []int{8, 3, 7, 4, 9, 1, 5}

insertionSort(a)

2 Treat the first value as already sorted

A hand of one card is in order, so start picking up from the second.

for i := 1; i < len(a); i++ {
    // place a[i] into the sorted part
}

3 Pick up the next value

Copy it out first. You are about to shuffle slots around, and without the copy it would be overwritten.

v := a[i]
j := i - 1

4 Slide bigger values one slot right

Walk backwards through the sorted part. Every value bigger than the one in your hand shifts right to make room.

for j >= 0 && a[j] > v {
    a[j+1] = a[j]
    j--
}

5 Drop it into the gap

The walk stops at a value that is not bigger, so the slot just after it is where your value belongs.

a[j+1] = v

The whole program

Put it together and the slice comes out sorted in place, smallest to largest.

package main

import "fmt"

func insertionSort(a []int) {
    for i := 1; i < len(a); i++ {
        v := a[i]
        j := i - 1

        for j >= 0 && a[j] > v {
            a[j+1] = a[j]
            j--
        }

        a[j+1] = v
    }
}

func main() {
    a := []int{8, 3, 7, 4, 9, 1, 5}
    insertionSort(a)
    fmt.Println(a)
}

Terminal

$ go run main.go
[1 3 4 5 7 8 9]

Previous Bubble Sort Next Topic Graph