Insertion sort works like sorting playing cards in your hand: the left part is already sorted, and every new element is inserted into its place in that part. It is simple, stable, works in place and is very fast on nearly sorted data. For the vocabulary (stable, adaptive) see sorting properties.

Insertion sort on 5 2 4 6 1 3
Insertion sort on 5 2 4 6 1 3

The algorithm and the invariant

Take x = a[i] and shift every element of the sorted part a[:i] that is greater than x one position to the right. Put x into the gap. Invariant: before step i the part a[:i] consists of the original first i elements and is sorted.

python
a = [5, 2, 4, 6, 1, 3]
for i in range(1, len(a)):
    x = a[i]
    j = i - 1
    while j >= 0 and a[j] > x:
        a[j + 1] = a[j]
        j -= 1
    a[j + 1] = x
    print("insert", x, "->", a)
text
insert 2 -> [2, 5, 4, 6, 1, 3]
insert 4 -> [2, 4, 5, 6, 1, 3]
insert 6 -> [2, 4, 5, 6, 1, 3]
insert 1 -> [1, 2, 4, 5, 6, 3]
insert 3 -> [1, 2, 3, 4, 5, 6]

Implementation

The condition j >= 0 and a[j] > x checks the bound first and then compares. The strict > does not move equal elements, so the sort is stable.