A. Programming Concepts and Skills · Algorithm Design and Analysis

Insertion Sort

A3.4 C2.3 C2.1About 70 minutes

Learning goals

I can write insertion sort and trace it pass by pass.
I can state its loop invariant: after pass i, the first i + 1 elements are sorted.
I can count its comparisons and shifts in the best, worst and average cases.
I can sort an array of records by a key, and explain what a stable sort is.

Words to know

insertion sort
A sort that grows a sorted part at the front of the array, taking the next element (the key) and shifting larger sorted elements right until the key's place is found.

key (in a sort)
The element currently being inserted; also, the field records are sorted by.

pass
One run of the outer loop of a sort.

in place
Sorting inside the original array, using only a few extra variables.

stable sort
A sort that keeps elements with equal keys in their original relative order.

adaptive
Doing less work on input that is already nearly sorted.

How you sort a hand of cards

Pick up cards one at a time. Each new card slides into place among the cards already in your hand: past the bigger ones, stopping at the first smaller one. Your hand is always sorted; it just keeps growing. Most people sort cards this way without being taught.

That is insertion sort. Curriculum expectation A3.4 asks you to create a sort algorithm such as bubble, insertion or selection sort. You wrote selection sort and bubble sort in ICS3U (Sorting Algorithms: Selection Sort and Bubble Sort). Insertion sort is the third classic, and in practice it is often the best of the three.

Remember from Grade 11

Selection sort: each pass finds the smallest remaining element and swaps it into place. Always n(n − 1) ÷ 2 comparisons.
Bubble sort: each pass compares neighbours and swaps them if they are out of order, so the largest remaining element "bubbles" to the end.

Both are O(n²). Insertion sort is O(n²) too in the worst case, but it has a big advantage you will see below.

The algorithm

For each index i from 1 to n − 1:

Lift out key = a[i]. The part a[0..i − 1] is already sorted.
Starting at j = i − 1, while j >= 0 and a[j] > key: shift a[j] one place right (a[j + 1] = a[j]) and move left (j -= 1).
Drop the key into the gap: a[j + 1] = key.

Loop invariant: at the start of pass i, a[0..i − 1] holds the elements that were originally in those positions, in sorted order. Each pass inserts one more element, so after the last pass the whole array is sorted (the postcondition).

def insertion_sort(a):

"""Sort the list a in place, in ascending order.

Precondition: the elements of a can be compared with >.

Postcondition: a holds the same elements in ascending order

(equal elements keep their original order); returns None.

"""

for i in range(1, len(a)):

key = a[i]

j = i - 1

while j >= 0 and a[j] > key:

a[j + 1] = a[j] # shift the bigger element right

j -= 1

a[j + 1] = key # drop the key into the gap

nums = [7, 3, 9, 1, 5]

insertion_sort(nums)

print(nums)

Output: [1, 3, 5, 7, 9]. The j >= 0 test comes first, so a[-1] is never read: and stops as soon as one side is False.

Inside one pass. The key (1) is lifted out, the larger sorted elements shift one place right, and the key drops into the gap.

The whole sort. The shaded sorted part grows by one element each pass; the yellow cell is where that pass's key landed. Pass 2 needed no shifting at all, because 9 was already bigger than everything before it.

Pass i	key	Comparisons	Shifts	Array after the pass
1	3	1 (7 > 3)	1	[3, 7, 9, 1, 5]
2	9	1 (7 > 9? no)	0	[3, 7, 9, 1, 5]
3	1	3 (9, 7, 3 all > 1; then j = −1)	3	[1, 3, 7, 9, 5]
4	5	3 (9 > 5, 7 > 5, 3 > 5? no)	2	[1, 3, 5, 7, 9]
Total		8	6

A comparison is one test of a[j] > key. When j reaches −1 the loop stops without a comparison.

Analysis: count comparisons and shifts

Best case: already sorted. Each pass makes 1 comparison and no shifts: n − 1 comparisons, O(n). Selection sort can never do this, and bubble sort matches it only with an early-exit check (see the next lesson); insertion sort is adaptive.
Worst case: reverse order. The key must travel all the way to the front on every pass: 1 + 2 + … + (n − 1) = n(n − 1) ÷ 2 comparisons and shifts, O(n²).
Average case (random order): each key travels about halfway back: about n² ÷ 4 comparisons. Still O(n²), but about half the work of selection sort.

The number of shifts equals the number of inversions: pairs of elements that are out of order. A nearly sorted array has few inversions, so insertion sort is fast on it. That is why real libraries (including Python's own sort, Timsort) use insertion sort for small or nearly sorted pieces.

def insertion_sort_count(a):

comparisons = shifts = 0

for i in range(1, len(a)):

key = a[i]

j = i - 1

while j >= 0:

comparisons += 1

if a[j] > key:

a[j + 1] = a[j]

shifts += 1

j -= 1

else:

break

a[j + 1] = key

return comparisons, shifts

n = 100

print("sorted: ", insertion_sort_count(list(range(n))))

print("reversed:", insertion_sort_count(list(range(n, 0, -1))))

print("one swap:", insertion_sort_count([0, 1, 2, 4, 3] + list(range(5, n))))

Output, one line each: sorted: (99, 0), reversed: (4950, 4950), one swap: (100, 1). For n = 100: 99 comparisons when sorted; 4950 = 100 × 99 ÷ 2 when reversed. One pair out of place adds just 1 comparison and 1 shift.

Sorting records, and stability

To sort records, compare a key field instead of the whole element. Insertion sort uses > (not >=), so a key only moves past elements that are strictly bigger. Elements with equal keys never pass each other: the sort is stable.

Stability matters when you sort by more than one field. Sort skiers by name first, then (stably) by club: within each club, names stay alphabetical.

def sort_by(records, field):

"""Stable insertion sort of a list of dictionaries by one field."""

for i in range(1, len(records)):

key = records[i]

j = i - 1

while j >= 0 and records[j][field] > key[field]:

records[j + 1] = records[j]

j -= 1

records[j + 1] = key

skiers = [

{"name": "Thomas", "club": "Whistler"},

{"name": "Aanya", "club": "Blue Mountain"},

{"name": "Maya", "club": "Blue Mountain"},

{"name": "Liam", "club": "Mont Tremblant"},

{"name": "Chloe", "club": "Whistler"},

]

sort_by(skiers, "name")

sort_by(skiers, "club")

for s in skiers:

print(s["club"], "-", s["name"])

Output, one line each: Blue Mountain - Aanya, Blue Mountain - Maya, Mont Tremblant - Liam, Whistler - Chloe, Whistler - Thomas. Because the second sort is stable, the names inside each club stay in the alphabetical order from the first sort.

Worked example

Descending order and a different key

Change insertion sort so it sorts a list of city records by population, largest first. Trace the first two passes on populations [1 017 000, 2 794 000, 569 000] (approximate 2021 census figures for Ottawa, Toronto and Hamilton).

To sort descending, move the key past elements that are smaller: change a[j] > key to a[j]["pop"] < key["pop"].
Pass 1: key = Toronto (2 794 000). Compare with Ottawa: 1 017 000 < 2 794 000, so shift Ottawa right; j = −1, so Toronto goes to index 0. Now [Toronto, Ottawa, Hamilton].
Pass 2: key = Hamilton (569 000). Compare with Ottawa: 1 017 000 < 569 000? No, so stop. Hamilton stays at index 2.
Result: Toronto, Ottawa, Hamilton. 2 comparisons, 1 shift.

Use < on the population field for descending order. The list becomes [Toronto, Ottawa, Hamilton] after 2 comparisons and 1 shift.

In real programs

Python's sorted(records, key=lambda r: r["pop"], reverse=True) and list.sort(...) are stable, O(n log n) and much faster than anything you write in Python. Use them in projects. Write your own sort when the curriculum or an interview asks you to create one, when you need to count operations, or when you work in an environment without a library.

Just for fun

Insertion sort at a party: every new guest walks in, looks at the line of people sorted by height, and politely steps past everyone taller until they find their spot.

Bubble sort at a party: everyone keeps swapping places with their neighbour until the host gives up and orders pizza.

Hands-on activity

Sort a hand, count the moves

You need: a deck of playing cards (use the Ace to 10 of one suit, Ace = 1), a pencil and paper, and a computer with Python.

Shuffle the 10 cards and deal them face up in a row. Write the order down.
Insertion sort them exactly like the algorithm: take the 2nd card as the key, slide bigger cards one place right, drop the key in. Then the 3rd card, and so on. Tally every comparison and every shift.
Type the same starting order into insertion_sort_count and check your tallies.
Count the inversions of your starting order by hand (pairs where a bigger card comes before a smaller one). Is it equal to your number of shifts?
Deal the cards in order 1 to 10, then swap two neighbours. Sort again. How many comparisons and shifts now?
Finally, deal them in reverse order (10 to 1) and predict the counts before you sort: 45 and 45.

What to look for: shifts = inversions every time; the nearly sorted hand takes only 10 comparisons (9 + 1) and 1 shift; the reversed hand takes 45 of each.

Your turn

Trace insertion sort on [4, 2, 5, 1]. Show the array after each pass.

How many comparisons and shifts does insertion sort make on [4, 2, 5, 1]?

What is the loop invariant of insertion sort?

Why must the loop test be j >= 0 and a[j] > key in that order?

Give the comparisons for insertion sort on a sorted list of 50, and on a reversed list of 50.

Is insertion sort stable? What change would make it unstable?

Which of the three sorts (selection, bubble, insertion) would you choose for a list that is already almost sorted, and why?

More practice: warm-up

In pass i, which part of the array is already sorted?

What is the best case for insertion sort, and its Big-O?

What is the worst case, and its Big-O?

What does "in place" mean?

Count the inversions in [3, 1, 2].

More practice: on your own

Write insertion sort so it sorts a list of strings ignoring capital letters (e.g. "apple" before "Banana").

How many shifts does insertion sort make on [5, 1, 4, 2, 3]? (Hint: count inversions.)

A list of 1000 numbers is sorted except that the last element is the smallest. How many comparisons does insertion sort make?

Predict the output:

a = [3, 1, 2]

for i in range(1, len(a)):

key = a[i]

j = i - 1

while j >= 0 and a[j] > key:

a[j + 1] = a[j]

j -= 1

a[j + 1] = key

print(a)

Records are sorted by sort_by(recs, "grade") and then by sort_by(recs, "last_name"). What order results?

Challenge

Prove that insertion sort's number of shifts equals the number of inversions in the input.

Binary insertion sort uses binary search to find where the key goes in a[0..i − 1]. How many comparisons and shifts does it make in the worst case? Is it O(n log n)?

Write a recursive insertion sort: to sort a[0..n − 1], first sort a[0..n − 2] recursively, then insert a[n − 1]. What is the base case? (Recursion is taught in Thinking Recursively: Base Cases and the Call Stack.)

Check your understanding

Quiz

After pass i of insertion sort, which statement is always true?

How many comparisons does insertion sort make on an already sorted list of 20 elements?

What is the result of the first pass of insertion sort on [8, 2, 6, 4]?

What makes a sort stable?

The number of shifts insertion sort makes is equal to:

Which input makes insertion sort do the most work?

For parents and teachers

Big idea: A3.4 asks students to create a sort algorithm (bubble, insertion or selection). Students already wrote selection and bubble sort in ICS3U, so this lesson adds insertion sort and analyses it (C2.3), with its contract and loop invariant (C2.1).

How to help: The card activity is the best support: ask your teen to say "compare, shift, compare, drop" out loud. Then ask, "Which hand was fastest to sort, and why?"

Common difficulties:

Writing the inner-loop condition in the wrong order (a[j] > key and j >= 0), which reads a[−1].
Forgetting the final a[j + 1] = key, or writing a[j] = key (off by one).
Confusing insertion sort's invariant (first part sorted among themselves) with selection sort's (first part holds the smallest elements).
Using >=, which makes the sort unstable and does extra shifts.