Sorting Algorithms
Three different ways to put a list of numbers in order, each with the same job, but a completely different strategy. Watch each one think, step by step, then compare how much work each actually does.
Bubble Sort
Compare each pair of neighbours; swap them if they're in the wrong order. Repeat passes over the list until a whole pass makes no swaps, that's how it knows it's finished.
Code
Controls
Why O(n²)?
A loop inside a loop, where both depend on n, is the biggest tell for O(n²). For our 9-item list, the worst case is (9×8)/2 = 36 comparisons, exactly what the counter showed on a reversed list. That nested-loop shape is worth spotting on sight in any pseudocode you're given.
Exam tips
- Compares adjacent pairs, swapping if out of order, over repeated passes.
- Worst/average case: O(n²). Best case (already sorted, with early exit): O(n).
- Stable, equal values keep their original relative order.
- In-place, no significant extra memory needed beyond the original list.
Insertion Sort
Build up a sorted section one element at a time. Take the next value, and slide it backwards past anything bigger until it finds its correct spot, like sorting playing cards in your hand.
Code
Controls
Why also O(n²)?
Same nested-loop shape as bubble sort: for each of the n elements, the inner while-loop might shift it past almost all the others. Worst case (reversed list): also (9×8)/2 = 36 comparisons. But notice the best case, an already-sorted list needs only 8 comparisons, one per element, because the inner loop exits immediately every time. That's genuinely adaptive behaviour, not just an add-on optimisation.
Exam tips
- Builds a sorted section at the front, inserting each new value into place.
- Worst/average case O(n²); best case (already sorted) O(n).
- Stable and in-place, like bubble sort.
- Often genuinely the fastest simple sort for small or nearly-sorted lists: this isn't just theory, it's why real languages sometimes fall back to it for small sub-arrays.
Merge Sort
This one's recursive, split the list in half, sort each half (by calling itself), then merge the two sorted halves back together. Watch the call stack: it's the exact same pattern as the recursion you've already met.
Code
Call stack
Controls
Why O(n log n)?
Merge sort halves the list every time it splits, and you can only halve 9 items about log₂(9) ≈ 3.17 times before reaching single elements (9 → 4/5 → 2/3 → 1). That's the "levels of splitting" you saw in the call stack. At every level, merging still touches all n items once. Total work ≈ n items × log₂(n) levels: that's where n log n comes from.
Exam tips
- Splits recursively to single elements, then merges pairs back in order.
- O(n log n) in the best, average, AND worst case, the starting order barely matters, unlike bubble/insertion sort.
- Stable, if the merge step prefers the left half on a tie (as ours does).
- Not in-place, needs extra memory (O(n)) to hold the left/right halves during merging. That's the trade-off for its speed guarantee.
Stability: does the order of equal values survive?
A sort is stable if two equal values keep their original relative order after sorting. This matters more than it sounds, imagine sorting exam results by score, where some students are tied: a stable sort keeps tied students in their original (say, alphabetical) order; an unstable one might shuffle them.
Input order
Output after sorting (bubble, insertion, or merge, all three agree)
Notice 2b still comes before 2e, and 5a still comes before 5c, exactly as they were in the input. All three algorithms here are stable, because each one only swaps when a value is strictly greater than the next (never swapping on equality). Change that one comparison from > to >= and you'd break stability, even though the list would still end up correctly sorted by value.
How much work does each one actually do?
Same 9-number list, three algorithms. Notice bubble sort and insertion sort both do very little work when the list is already almost sorted, but bubble sort's comparisons barely change on a reversed list, while merge sort barely changes at all between cases.
| Case | Bubble compares | Bubble swaps | Insertion compares | Insertion shifts | Merge compares |
|---|---|---|---|---|---|
| Typical (demo list) | 30 | 16 | 22 | 16 | 21 |
| Best case (already sorted) | 8 | 0 | 8 | 0 | 13 |
| Worst case (reversed) | 36 | 36 | 36 | 36 | 16 |
Merge sort's comparisons barely move between best and worst case, that consistency is exactly why it's rated O(n log n) rather than O(n²), regardless of the starting order.