An insertion sort builds a sorted part at the front of the list, taking the next item each time and sliding it back to where it belongs. You write and trace it in pseudocode, then compare it with the bubble sort for different starting orders and sizes of data.
An insertion sort treats the first element as a sorted part of length one. Each pass takes the next element as the key, compares it with the sorted part from right to left, shifts every larger element one place to the right, and drops the key into the gap. After pass i the first i elements are in order. On data that is already sorted each pass makes one comparison, so it needs only n − 1 comparisons; on data in reverse order it needs n(n − 1)/2. The bubble sort has the same best and worst cases, but usually makes more comparisons and moves data with three-step swaps.
Fig. 1: an insertion sort of five integers, shown after each pass; 8 comparisons in total
Section 01
Build a sorted part.
In the lab, step through an insertion sort. Each pass lifts out one item (the key), shifts larger items in the sorted part one place right, and places the key in the gap. Count the comparisons on random data, then on sorted data.
Start: a list of one item is already sorted, so the first pass takes the second element as the key.
Compare and shift: while the element to the left of the gap is larger than the key, copy it one place right. Stop at the first element that is not larger, or at the start of the list.
Insert: put the key in the gap left by the last shift. Nothing is swapped: each larger item moves once, and the key is written once.
Passes: n − 1 passes for n items. After the last pass the whole list is sorted.
Worked example One pass in detail
After two passes, Nums holds 12, 27, 35, 8, 19 (Fig. 1). Describe pass 3, which inserts the key 8.
Key ← 8, the element in position 4. The sorted part is 12, 27, 35.
35 > 8: shift 35 into position 4. 27 > 8: shift 27 into position 3. 12 > 8: shift 12 into position 2.
The start of the list has been reached, so the loop stops: 3 comparisons and 3 shifts.
Write the key into position 1.
Answer: Nums holds 8, 12, 27, 35, 19; the first four elements are now sorted
Your turn
Do the final pass: insert the key 19 into 8, 12, 27, 35. How many comparisons are made?
Do not describe an insertion sort as "comparing adjacent pairs and swapping them": that is a bubble sort. Say that each item is inserted into its correct position in the sorted part.
Section 02
Write it in pseudocode.
The outer FOR loop chooses the key; the inner WHILE loop shifts larger items right. Learn the line List[j + 1] ← Key at the end: it is the mark examiners look for.
DECLARE List : ARRAY[1:6] OF INTEGER
DECLARE i : INTEGER
DECLARE j : INTEGER
DECLARE Key : INTEGER
FOR i ← 2 TO 6
Key ← List[i]
j ← i - 1
WHILE j >= 1 AND List[j] > Key
List[j + 1] ← List[j]
j ← j - 1
ENDWHILE
List[j + 1] ← Key
NEXT i
Key: saved before any shifting, because the first shift overwrites List[i].
j >= 1: stops j running off the front of the array when the key is the smallest value so far. (If your language checks both conditions even when the first is FALSE, use a Boolean flag instead so List[0] is never read.)
Descending order: change List[j] > Key to List[j] < Key.
Worked example Full trace
List holds 14, 6, 22, 3, 17, 9. Show the list after each pass of the insertion sort and count the comparisons (evaluations of List[j] > Key).
A 4-element array holds 4, 9, 2, 7. What does it hold after the pass with i = 3, and how many comparisons does the whole sort make?
After i = 2: 4, 9, 2, 7 (1 comparison). After i = 3: 2, 4, 9, 7 (2 comparisons). After i = 4: 2, 4, 7, 9 (2 comparisons). Total 5.
Examiner trap
Writing List[j] ← Key after the loop puts the key one place too far left. When the loop stops, j points at the element that is not larger, so the gap is at j + 1.
Stage 1 · Learn
Check what the sim just showed you
Four quick checks. Each correct answer earns XP and records this skill on your profile.
Quick check+10 XP
In the lab, which element becomes the key on the first pass of an insertion sort?
Quick check+10 XP
During one pass, what happens to each element of the sorted part that is larger than the key?
Quick check+10 XP
Why is Key ← List[i] done before the WHILE loop starts?
Quick check+10 XP
An insertion sort is run on 8 items that are already in order. How many comparisons does it make?
Section 03
Which sort, and when?
The syllabus says the performance of a sorting routine may depend on the initial order of the data and the number of items. In the lab, compare the two sorts on random, sorted and reversed data and watch how the counts grow with n.
Starting order (n items)
Insertion sort comparisons
Improved bubble sort comparisons
Already sorted (best case)
n − 1
n − 1 (one pass, no swaps, stop)
Reverse order (worst case)
n(n − 1)/2
n(n − 1)/2
27, 12, 35, 8, 19 (n = 5)
8
10
Reverse order, n = 100
4950
4950
Initial order: both sorts are fast on data that is nearly sorted and slow on data in reverse order. Insertion sort is especially good when a few new items are added to a list that is already sorted.
Number of items: in the worst case the comparisons grow with n2: ten times the data means about a hundred times the work. Both are O(n2) in the worst and average case and O(n) in the best case.
Data movement: a bubble sort swap needs three assignments; an insertion sort shift needs one, so insertion sort usually does less work.
Memory: both sort in place, using one or two extra variables (Temp or Key) whatever the size of the list.
Worked example Predict the work
An insertion sort takes 0.2 seconds to sort 2000 records that are in reverse order. Estimate the time for 6000 records in reverse order, and for 6000 records that are already sorted.
In the worst case the work grows with n2. 6000 is 3 times 2000, so the work is about 32 = 9 times as much.
Reverse order: 0.2 × 9 = 1.8 seconds.
Already sorted: only n − 1 comparisons, growing with n, so the time is tiny compared with the worst case.
Answer: About 1.8 s in reverse order; a small fraction of a second when already sorted
Your turn
How many comparisons does an insertion sort make on 10 items in reverse order? And on 10 items already sorted?
"Insertion sort is faster than bubble sort" earns little on its own. Link the answer to the data: for nearly sorted data both are quick, and in the worst case both need n(n − 1)/2 comparisons.
Stage 2 · Exam
Exam-style questions
Unlocks once the four checks above are done. Worth more XP, written to A Level Paper 3 and Paper 4 standard.
Finish the four checks above to unlock the exam questions
Exam style+20 XP
How many comparisons does an insertion sort make on 6 items in reverse order?
Exam style+20 XP
For which data is an insertion sort most efficient?
Exam style+20 XP
Which line places the key after the inner WHILE loop has finished?
Exam style+20 XP
A sort takes 1 second for 1000 items in the worst case and is O(n2). About how long for 4000 items in the worst case?
Skill unlocked
Insertion sort, mastered.
This skill is now recorded on your profile. Keep the chain going.