Five lessons, because there is no single best sort. Written to the course standard — prerequisites, observable outcomes, worked derivations, a runnable lab whose output was generated from an actual run, practice with hidden answers, and a demonstrable finish line.
Why this is a folder and not one note. “Sorting” is not one algorithm; it is a family with genuinely different trade-offs. Merge sort guarantees and costs memory. Quicksort is faster in practice and has a quadratic worst case on the most common input shape there is. Counting sort is linear but needs small integer keys. Choosing well means knowing which property each one buys and what it charges.
Reading order
- Sorting and the $\Omega(n\log n)$ Lower Bound — [Intermediate] — stable, in-place, adaptive; the decision-tree proof that no comparison sort can do better; the master comparison table
- Elementary Sorts — [Beginner] — bubble, selection, insertion, each with its loop invariant; why insertion sort is inside every production library
- Merge Sort — [Intermediate] — divide and conquer, guaranteed , stable, and the basis of external sorting when data exceeds memory
- Quicksort — [Advanced] — Lomuto and Hoare partitioning, the worst case triggered on purpose, median-of-three, introsort, three-way partitioning
- Non-Comparison Sorts — [Intermediate] — counting, radix and bucket sort, and how they legitimately get under the bound
The comparison table
| Algorithm | Best | Average | Worst | Space | Stable | Adaptive | Use it when |
|---|---|---|---|---|---|---|---|
| Bubble | ✅ | ✅ | Teaching only | ||||
| Selection | ❌ | ❌ | Writes are expensive | ||||
| Insertion | ✅ | ✅ | , or nearly sorted | ||||
| Merge | ✅ | ❌ | Guarantee needed; linked lists; external | ||||
| Quick | ❌ | ❌ | General in-memory default | ||||
| Heap | ❌ | ❌ | Guarantee and no extra memory | ||||
| Counting | ✅ | ❌ | Small integer key range | ||||
| Radix | ✅ | ❌ | Fixed-width integer or string keys |
Choosing, in one page
- Just sort it → your language’s built-in. Python’s Timsort is stable and adaptive; C++‘s introsort is fast with a hard ceiling.
- Need stability → merge family. Never quicksort or heapsort.
- No spare memory → heapsort, or quicksort with tail-recursion elimination.
- Need a worst-case guarantee → merge or heap. Quicksort only with introsort’s fallback.
- Data larger than RAM → external merge sort.
- Small integer keys → counting or radix, and beat the bound.
- Nearly sorted already → insertion, or Timsort, which detects runs.
- Only need the th element → do not sort. Quickselect is .
What is verified
Every lab was executed and its expected output generated from that run. Several test a claim rather than illustrate one:
- The lower bound is about the worst case — merge sort on random input exceeds , while on reversed input it does fewer comparisons, which is a best case, not a contradiction.
- Loop invariants asserted on every pass of all three elementary sorts, over 200 random arrays each.
- Selection sort’s instability shown, using a class that compares on the key alone — comparing plain tuples would make every sort look stable.
- Merge sort’s write count is identical for sorted, reversed, random and all-equal input.
- Stability turns on one character —
<=versus<in the merge. - Quicksort’s worst case triggered deliberately: 79,800 comparisons and depth 399 on sorted input against 3,420 and depth 16 on random, then fixed by median-of-three.
- Radix sort with an unstable inner sort produces an unsorted array, demonstrating why that dependency is load-bearing.
- Bucket sort collapsing on clustered input: 4,996 items in one bucket against a uniform 122.
Question banks
One bank per lesson: micro-questions with the answers hidden behind toggles, for closed-book recall rather than reading. Method explained in the arrays bank.
Related
- 03-algorithms — the parent folder
- Complexity Analysis — the notation used throughout
- Searching — what sorting enables
- Heaps — heapsort, and the -way merge’s engine
- 04-patterns — where sorting shows up as a problem-solving move
Software engineering
Infrastructure & security
Computer science
Hardware & engineering