Insertion Sort

Build a sorted section at the front, inserting each item into place.

An insertion sort builds a sorted section at the front of the list. It takes each item in turn and inserts it into its correct place among the items already sorted. It works much like sorting a hand of playing cards.

The idea

Picture sorting cards in your hand. You pick up each new card and slide it left until it sits in the right place among the cards you have already arranged. Everything to the left stays sorted; everything to the right is still waiting.

already sortedthe gap left by the itemitem being inserted

Inserting one item

To insert an item, compare it with the sorted items to its left. Every item that is larger shifts one place to the right to make room, until the item reaches its slot. Here is the 5th pass, inserting 8 into the sorted front [3, 4, 5, 9, 15].

take out 8 to insert

345915112

15 > 8 → shift 15 right

345915112

9 > 8 → shift 9 right

345915112

5 < 8 → insert 8 here

3458915112

The sorted front has grown from five items to six. The same process repeats for every item.

Insertion sort in Python

insertion.py

alist = [9, 5, 4, 15, 3, 8, 11, 2]

for index in range(1, len(alist)):
    current = alist[index]
    pos = index
    while pos > 0 and alist[pos - 1] > current:
        alist[pos] = alist[pos - 1]
        pos = pos - 1
    alist[pos] = current

print(alist)

Output

[2, 3, 4, 5, 8, 9, 11, 15]

How it works

index steps through the list from the second item (index 1) to the end.
current is the item being inserted; pos tracks where it will go.
The while loop shifts each larger sorted item one place right with alist[pos] = alist[pos - 1].
When a smaller item is reached (or the start of the list), current drops into pos.

Here is the sorted front (gold) growing by one item after each pass:

sorted section

pass 1 — insert 5

5941538112

pass 2 — insert 4

4591538112

pass 3 — insert 15

4591538112

pass 4 — insert 3

3459158112

pass 5 — insert 8

3458915112

pass 6 — insert 11

3458911152

pass 7 — insert 2

2345891115

Bubble sort or insertion sort?Insertion sort usually does less work than bubble sort, especially on a list that is already nearly sorted — it stops shifting as soon as an item is in place. Both are still slow on large, randomly-ordered lists.

What you have learned

An insertion sort grows a sorted section at the front, inserting each new item into place.
Larger sorted items shift right to make room for the item being inserted.
It is efficient on small or nearly-sorted lists.
Like bubble sort, it becomes slow on large lists.