The Sorting Family Tree: Bubble to Quicksort, and What They All Trade

Hook #

Sorting is the first algorithm you learned, probably in some loop-with-swaps form, and it's the algorithm with more named variants than any other. Bubble, selection, insertion, merge, quick, heap, Tim, intro, counting, radix, bucket — at least eleven sorts you'll meet, each with a place. The reason there are so many isn't that CS researchers got bored. It's that sorting is the workload where the constants matter as much as the asymptotics, and different inputs reward different strategies. This lesson is a tour of the comparison-based sorting family — what they share, what they trade, and why your standard-library sort is almost certainly a hybrid.

What you'll be able to do by the end of this lesson #

• Distinguish the simple sorts (bubble, selection, insertion — O(n²) average) from the efficient sorts (merge, quicksort, heap sort — O(n log n) average).
• Predict the runtime of merge sort using the master theorem from Course 1.2 lesson 4.
• Explain why insertion sort, despite being O(n²) average, is the fast choice for arrays under ~20 elements.
• Identify three properties that distinguish sorting algorithms: stable vs unstable, in-place vs out-of-place, adaptive (faster on partially-sorted input) vs not.
• Recognise what a hybrid sort (Timsort, introsort) is and why every modern standard-library sort is one.

Why this matters here #

Sorting is the workhorse of structured-data processing. Every database query with ORDER BY is a sort. Every "top 10 results" is a partial sort. Every histogram bucket arrangement, every UI list ordering, every priority-by-time event scheduler is a sort. The cost of sorting determines a lot of system latencies — and the choice of algorithm matters, because the right one is 2-5x faster than the wrong one on typical workloads.

A second reason: sorting is the family of algorithms where the algorithm and the data interact strongly. An array of random integers is sorted differently than an array that's "almost sorted with a few out-of-place elements" — the second case is what insertion sort and Timsort are designed for, and they crush the textbook merge-sort/quicksort on it. The general lesson — the right algorithm depends on the input distribution — recurs in everything from compiler optimisation to ML model selection.

CS61B and Abdul Bari cover this material more thoroughly than any single lesson here ever will. We frame to point you to them with the engineer's-lens framing that makes the algorithm choice purposeful rather than memorised.

The engineer's lens #

Four things the canonical resources teach but don't put a name on:

1. The three properties that organise the sorting menu. Every sort can be classified along three axes:

• Stable = elements with equal keys preserve their original order. Matters when you sort by multiple keys in sequence (sort by name, then sort by age — stability preserves the name-order ties).
• In-place = uses O(1) or O(log n) extra space rather than O(n). Matters when memory is constrained.
• Adaptive = runs faster on partially-sorted input. Matters because real inputs are almost always partially sorted; uniform-random arrays only exist in textbook problems.

The combination of axes is what makes Timsort dominate as the default library sort: stable, adaptive, O(n log n) worst case. The cost is O(n) extra space, which on modern hardware is acceptable.

2. Insertion sort is the surprise hero for small arrays. Insertion sort is O(n²) average — strictly worse than merge or quicksort. But for arrays of size ≤ ~16 elements, insertion sort is faster in absolute wall-clock time. Two reasons:

• No recursion overhead. Merge sort and quicksort have function-call overhead per recursive call. For small arrays, the recursive calls dominate the actual sorting work.
• Cache-friendly tight loop. Insertion sort's inner loop is a few instructions on adjacent memory locations. The CPU prefetcher and branch predictor handle it beautifully. Merge sort's merge step has scattered memory accesses by comparison.

This is why every production sort algorithm has a threshold (typically 16-32) below which it falls back to insertion sort. Timsort uses insertion sort for runs ≤ 32. Introsort uses it for partitions ≤ 16. Java's Arrays.sort falls back at 47. The fast-on-large hybrid is built around this small-array optimisation.

3. Quicksort's "worst case is O(n²)" is the central engineering problem. Standard quicksort picks a pivot, partitions the array, recurses on both halves. Expected O(n log n) — but a bad pivot (always the smallest or largest element) gives partitions of size 0 and n-1, which is O(n²). On adversarial input (already-sorted arrays, with the first element as pivot), quicksort systematically hits this worst case.

The fixes:

• Random pivot — pick a random element as pivot. Makes the worst case probabilistically impossible (still O(n²) worst case in theory; vanishingly rare in practice).
• Median-of-three — pick the median of first, middle, last as pivot. Cheap; eliminates the "sorted input" pathology specifically.
• Introsort — start with quicksort; if recursion depth exceeds 2 log n (suggesting bad pivot luck), switch to heap sort, which is guaranteed O(n log n). Combines quicksort's cache friendliness with heap sort's worst-case guarantee.

C++'s std::sort is introsort. Rust's slice.sort_unstable is introsort. The bad-pivot problem is solved; the cost is one runtime check per recursion.

4. Merge sort wins on external sorting, where data doesn't fit in RAM. Sorting 1 TB of data that lives on disk — merge sort is the answer. The reason: merge sort's pattern (split, sort halves, merge) maps directly to "read two sorted chunks from disk, merge them streaming into one larger chunk." Quicksort needs random access to the full array; on disk, that's millions of slow seeks. Merge sort needs only sequential access; the OS and disk love sequential.

The external merge sort algorithm (used by every database for ORDER BY on tables that exceed RAM) is merge sort with a tuning knob: instead of recursing all the way to single-element arrays, sort chunks of "as much as fits in RAM" using an in-memory sort (probably quicksort), then merge the sorted chunks from disk. The in-memory sort handles ~1 GB; the merge handles arbitrary scale.

What to focus on in the canonical resources #

The body of sorting material is large; here's the load-bearing slice:

• CS61B's merge sort + quicksort lectures. ~90 minutes. The recurrence analysis is the math; the partitioning visual is the algorithm. Both are essential.
• Abdul Bari's videos — pick three to watch: insertion sort (the simple-but-adaptive baseline), merge sort (divide and conquer concrete), quicksort (the partitioning trick). ~75 minutes total.
• Visualgo — type in three input arrays and watch each algorithm: (a) random, (b) already-sorted, (c) reverse-sorted. The contrast between adaptive (insertion, Timsort) and not-adaptive (selection, merge) is most visible on input (b).
• Tim Peters's listsort.txt — read once. It's a design document for production code. The galloping-mode discussion is genuinely interesting engineering; the "natural runs" insight is the load-bearing idea behind why Timsort wins.

What to skip on first pass: - Bubble sort. Famous as "the bad sort"; you only need to know it exists. Insertion sort dominates it on every axis. - Shell sort. An interesting historical sort that uses a sequence of insertion-sort passes with decreasing gaps. Rare in practice; covered if you have time. - Sample sort, parallel sorts. Important for distributed systems; covered in Course 7.x.

What to come back with #

Three predictions before practising:

1. Trace insertion sort by hand on [5, 2, 4, 6, 1, 3]. Show the array after each pass. Count the comparisons. Now do the same for [1, 2, 3, 4, 5, 6] (already sorted). The contrast — fewer comparisons on sorted input — is the adaptive property in action.

2. Predict the running time of quicksort on: a. A random array of 1 million ints. b. An already-sorted array of 1 million ints, with naive first-element-as-pivot. c. An already-sorted array of 1 million ints, with median-of-three pivot.

For each, name the algorithm class (O(n log n) or O(n²)) and give a wall-clock estimate (microseconds, milliseconds, seconds, minutes).

1. Which sort would you use for: a. Sorting 50 items in a tight inner loop. b. Sorting 100 million 32-bit integers, all in memory. c. Sorting a 1 TB log file on disk. d. Sorting strings by length, preserving original order for ties.

Where this connects #

Backward: Course 1.2 lesson 4 (Recurrences and the Master Theorem) is the math that gave you merge sort = T(n/2) + T(n/2) + O(n) = O(n log n). Course 2.2 lesson 5 (Heap Sort) gave you the third O(n log n) member of this family — the one with O(1) extra space but worse cache behaviour than quicksort. Course 2.1 lesson 4 (Stacks) is what underlies the recursive calls of merge sort and quicksort — every recursive sort consumes call-stack space proportional to the recursion depth.

Forward: Lesson 2 (Ω(n log n) lower bound) proves why you can't do better than n log n with comparisons. Lesson 3 (non-comparison sorts) is where you cheat the lower bound by using more than just comparisons. Lesson 4 (binary search) is the canonical algorithm that runs on sorted data — sort once, search many times. Lesson 5 (quickselect) takes quicksort's partition step and uses it for selecting the k-th element, not full sorting. Course 3.3 (Algorithm Design Paradigms) treats divide-and-conquer formally; merge sort is the canonical example. Course 8.x (Databases) revisits external sorting in the context of query execution.

The zc-sorting-algorithm-benchmark-suite project for this course has you implement and benchmark several sorts on different input distributions. After this lesson, the project becomes the empirical check on the trade-offs the lesson describes — and the contrast between predicted asymptotic cost and actual wall-clock time is where the engineer's-lens framing earns its keep.