4 · Insertion sort · DAA Study Hub

In one sentence

Insertion sort grows a sorted section on the left, one element at a time: take the next element (the key), slide bigger elements one step right, and drop the key into the gap. Best case $\Theta(n)$ (already sorted), worst case $\Theta(n^2)$ (reverse sorted).

Everyday analogy

Sorting a hand of playing cards. You pick up cards one by one. Each new card is slid leftwards past every card that's bigger than it, until it sits in the right place. The cards in your hand are always sorted, and that's the loop invariant.

The algorithm

InsertionSort(A, n)
1  for j ← 2 to n do
2      key ← A[j]
3      // insert A[j] into the sorted part A[1..j-1]
4      i ← j − 1
5      while i > 0 and A[i] > key do
6          A[i + 1] ← A[i]          // shift the bigger element right
7          i ← i − 1
8      A[i + 1] ← key               // drop key into the gap

(The slides call the outer variable j; CLRS 4e renames it i. The algorithm is the same.)

Loop invariant: whenever the outer loop is about to begin a pass with index j, the left part A[1..j-1] contains exactly the items that started there, now in sorted order.

Trace on [7, 3, 9, 1, 5] (our own example). Bold = the sorted part after the step.

Step	key	What happens	Array after	Shifts
start	—	`A[1..1]` is trivially sorted	7, 3, 9, 1, 5	—
$j = 2$	3	7 > 3 → shift 7 right; drop 3 at position 1	3, 7, 9, 1, 5	1
$j = 3$	9	7 > 9? no → stays put	3, 7, 9, 1, 5	0
$j = 4$	1	9, 7, 3 all > 1 → shift all three; drop 1 at front	1, 3, 7, 9, 5	3
$j = 5$	5	9, 7 > 5 shift; 3 > 5? no → drop 5 after 3	1, 3, 5, 7, 9	2

Total: 6 shifts and 8 key comparisons (A[i] > key checks).

Fun fact: the number of shifts always equals the number of inversions (pairs that are in the wrong order). Here they are (7,3), (7,1), (7,5), (3,1), (9,1), (9,5): 6 ✓

j = 4, key = 1
[3][7][9][1][5]      take key = 1, leaving a gap at position 4
[3][7][ ][9][5]      9 > 1 → shift right
[3][ ][7][9][5]      7 > 1 → shift right
[ ][3][7][9][5]      3 > 1 → shift right, i = 0 so stop
[1][3][7][9][5]      drop key into the gap

Common mistakes

Writing the best case as "small array". It means already sorted, for any $n$ .
Using $t_j = j - 1$ for the worst case of the while test. The test runs $j$ times (including the failing check); the shifts are $j - 1$ .
Forgetting the final A[i + 1] ← key in a trace, so the key "disappears".
An invariant that says "A[1..j-1] is sorted" but forgets "…and contains the original elements of A[1..j-1]".

Mastery check

Solve without hints, then explain

(a) Trace insertion sort on [4, 1, 3, 2], showing the array after each $j$ and counting shifts.

(b) Give a worst-case input of size 5 and its number of shifts.

Your mastery check

Not started

Solve the problem above with no hints, close the page and explain it out loud. Tick each step honestly.

Solved the mastery check with no hints

Said it in one sentence

Explained it with my own analogy

Walked through the steps of my own hand trace

Explained why it is correct / how fast it is

Named a trap a beginner would fall into

Status

Tick all six steps to unlock “Mastered”.

Which study mode worked for you?

Saved in this browser onlySee all my progress →

See it move

VisuAlgo: Sorting: pick INS (insertion sort) and step through your own array.

References

05-06 Insertion Sort & Analysis: Slides 4–5 (algorithm and trace), 6–7 (loop invariant and correctness), 10–13 (running time, best/worst case).
CLRS 4e §2.1 (insertion sort, loop invariant), §2.2 (running-time analysis). Homework from Slide 8: exercises 2.1-1 to 2.1-4. Hints available on request, no full solutions.

4 · Insertion sort

Everyday analogyCopy Anchor Link

The algorithmCopy Anchor Link

Common mistakesCopy Anchor Link

Mastery checkCopy Anchor Link

✅ Answers

See it moveCopy Anchor Link