Insertion Sort
Grow a sorted part on the left by inserting each new item into its correct place, like sorting cards in your hand. Fast on nearly sorted data.
Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.
02Mental model
You’re dealt cards one at a time. Your hand is always sorted: each new card slides left past the bigger ones until it finds its spot. You never re-sort the whole hand. That’s insertion sort.
The idea
- The part
a[0..i-1]is always sorted. - Take
key = a[i]. - Walk left from
i - 1, shifting every item bigger thankeyone place right. - When you hit an item ≤ key (or the start), drop
keyinto the gap.
Why it’s adaptive
If the array is already sorted, every key is ≥ its left neighbour, so the while loop stops at once: n − 1 comparisons, O(n). If it’s reversed, every key travels all the way to the front: n(n−1)/2, O(n²). The less “out of order” the data, the faster it runs.
Shift, don’t swap
Each step of the while loop is one assignment (a[j+1] = a[j]), not a three-assignment swap. That’s why insertion sort usually beats bubble sort in practice, even though both are O(n²).
03Visualize
space play · ←→ step · r reset. The highlighted code line follows each step.
Compare the "Sorted" preset (n − 1 comparisons) with "Reversed".
04C++ code
Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.
#include <iostream>
using namespace std;
void insertionSort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) { // shift bigger items right
a[j + 1] = a[j];
j--;
}
a[j + 1] = key; // drop key into the gap
}
}
int main() {
int a[] = {29, 10, 14, 37, 13, 5};
int n = sizeof(a) / sizeof(a[0]);
insertionSort(a, n);
for (int i = 0; i < n; i++) cout << a[i] << " ";
cout << "\n";
}5 10 13 14 29 37
05Complexity
| Best case (already sorted) | O(n): n − 1 comparisons, 0 shifts |
|---|---|
| Average case | O(n²) |
| Worst case (reversed) | O(n²): n(n−1)/2 comparisons and shifts |
| Extra space | O(1) |
| Stable? | Yes |
| In-place? | Yes |
Insertion sort is adaptive (faster on nearly sorted input) and online (it can sort items as they arrive). Real libraries use it for small sub-arrays.
06Watch
Insertion sort algorithm
Why this one: Builds the "shift right, then drop the key" loop carefully and analyses the cases.
Insertion sort in 2 minutes
Why this one: Two-minute animation to lock in the picture.
Original class slides (Python, by the course's lecture authors):Sorting Basics
07Exam lens
Likely questions
- Trace insertion sort on
12, 11, 13, 5, 6, showing the array after each insertion. - What are the best and worst case inputs and complexities of insertion sort?
- Why does insertion sort perform well on nearly sorted data?
- Compare insertion sort with selection sort.
Common mistakes
- Writing
a[j] >= keyin the while loop. That breaks stability. - Forgetting
j >= 0in the loop condition, which readsa[-1]. - Putting
a[j + 1] = keyinside the while loop. It goes after the loop. - Starting the outer loop at
i = 0. Item 0 alone is already "sorted", so start at 1.
08Quick check
09Practice
🟢 Trace by hand
Trace insertion sort on 12, 11, 13, 5, 6. Write the array after each value of i.
Show answer
- i = 1 (key 11):
11 12 13 5 6 - i = 2 (key 13):
11 12 13 5 6(no shift) - i = 3 (key 5):
5 11 12 13 6(3 shifts) - i = 4 (key 6):
5 6 11 12 13(3 shifts)
🟡 Implement it
Write insertionSortDesc (descending order), then a version that sorts an array of string names alphabetically.
Hint
Only the comparison changes. string supports < and > out of the box.
🔴 Solve problems
Hint
Same idea on a linked list. Use a dummy head for the sorted list and insert each node after the right predecessor (revisit after Chapter 4).
Hint
Insertion sort will time out on the large tests, which shows why O(n²) matters.
Hint
Print the array after every shift. A great tracing exercise.
10Mastery checklist
Tick these honestly. When every box is ticked, the topic is marked complete.