Comparison Sorts: Merge, Quick, and How Libraries Sort

The last two patterns ran on credit. Binary search threw away half a billion elements with a single comparison, and the license for that move was one word: sorted. The converging pair in lesson 7 retired one element per comparison on the same license. Both times, the sorted array just appeared, free of charge, and nobody asked where it came from.

Sorted data does not exist in nature. Logs arrive in arrival order. Users sign up in signup order. Every sorted array in production was paid for, by a sort, which makes sorting the purchase that funds half the techniques in this course. It's also the most studied problem in computer science, and this lesson buys it three ways: with merge sort, the cleanest recursive algorithm ever written; with quicksort, faster in practice and carrying a famous catastrophe; and then by opening your standard library to see what it actually runs, which is neither, and both.

This is also the lesson where two old promissory notes come due. Lesson 1's growth ladder had a rung labeled O(n log n), "halve-and-recombine over everything (good sorting)", and both lessons 1 and 2 flagged the oddity that real sorting libraries switch to a quadratic insertion sort below a few dozen elements. By the end of this page, the rung is derived and the oddity is fully cashed.

The quadratic shelf

Start at the bottom, because one of these refuses to die.

Selection sort is the obvious idea: scan everything, find the smallest, swap it to the front. Scan the rest, find the next smallest. n scans over a shrinking array is the n(n-1)/2 triangle from lesson 1: O(n²), no redeeming features beyond simplicity.

Insertion sort is the card player's idea: take the next element and slide it left, past everything bigger, until it sits in place.

function insertion_sort(items):
    for i from 1 to n-1:
        x = items[i]
        j = i - 1
        while j >= 0 and items[j] > x:
            items[j+1] = items[j]      # slide the bigger neighbor right
            j = j - 1
        items[j+1] = x                 # x lands in its slot

Worst case it's the same O(n²) triangle. But look at its virtues, because they're about to matter. If the input is already nearly sorted, each slide is one or two steps and the whole sort runs in nearly O(n): insertion sort is adaptive. It never reorders elements that compare equal (a property called stability, defined properly below). And every move touches immediate neighbors, which is exactly the access pattern lesson 2 crowned: at small sizes the whole array is two or three cache lines and insertion sort just slides values around inside L1.

Bubble sort, the one everyone learns first, repeatedly swaps adjacent out-of-order pairs. Same O(n²), and it has none of insertion sort's virtues while doing more writes. It lives in courses, not in libraries, and this is its only appearance in this one.

The shelf's price at scale is lesson 1's table: a million elements at O(n²) is about 2.8 hours. Fine for a hand of cards, dead past that.

Merge sort: trust the halves

So how do you sort a million elements in a fraction of a second? Lesson 9 handed you the tool: to write a recursive function, design the base case and one step, written as if the recursive call already works.

Apply the leap of faith to sorting. Base case: an array of one element is already sorted. The step: split the array in half, trust the recursion to hand back each half sorted, then combine two sorted halves into one sorted whole. That's merge sort, and it's old enough to be foundational in the most literal sense: John von Neumann worked it out in 1945 for one of the first stored-program computers.

Note the shape before anything else. The problem shrinks by half per call, so lesson 9's space bill is the friendly kind: O(log n) depth, about twenty frames for a million elements. The entire algorithm now rides on one question: how cheap is the combine step?

The merge

Two sorted halves: [3, 27, 38, 43] and [5, 9, 10, 82]. Put a pointer on the front of each. Lesson 7 taught the question to ask: is there a reason a pointer never needs to go back? Here it is. Each half is sorted, so the element under each pointer is the smallest thing left in its half. Compare the two: the smaller one is smaller than everything remaining in its own half and smaller than everything in the other half (which all sits behind a front it already beat). It is the minimum of everything left. So it's final: write it to the output, advance that pointer, never look back.

function merge(left, right):
    out = empty array
    i = 0, j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:        # <= : ties go left (stability, see below)
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    append the rest of left, then the rest of right
    return out

Run it: 3 vs 5, take 3. 27 vs 5, take 5. 27 vs 9, take 9. 27 vs 10, take 10. 27 vs 82, take 27, then 38, then 43, and the left half empties; copy the 82. Output: [3, 5, 9, 10, 27, 38, 43, 82]. Eight elements, seven comparisons, one pass. Merging is O(n), and that single fact makes the whole algorithm work.

The recursion tree

Now the full run on eight elements, [38, 27, 43, 3, 9, 82, 10, 5], watching the shape:

                [38 27 43  3  9 82 10  5]
               /                         \
       [38 27 43  3]                [9 82 10  5]
       /           \                /          \
  [38 27]        [43  3]       [9 82]       [10  5]
  /     \        /     \       /    \       /     \
[38]   [27]   [43]    [3]    [9]   [82]  [10]    [5]

Singles are the base case, sorted by definition. All the work happens on the unwind, exactly like lesson 9's factorial table, except here the unwind merges:

 [27 38]     [3 43]      [9 82]     [5 10]
       \     /                \     /
      [3 27 38 43]        [5 9 10 82]
              \              /
          [3 5 9 10 27 38 43 82]

Now the arithmetic, which is the whole reason this lesson exists:

Eight halves down to one in three doublings: log n levels. And at every level, each of the n elements passes through exactly one merge: n work per level. Total: n log n. That is lesson 1's "halve-and-recombine" rung, derived instead of asserted. At a million elements: 20 levels times a million moves is 20 million, the ~0.2 seconds row of the wall-time table, against the quadratic shelf's 2.8 hours.

What merge sort buys, and what it costs

The guarantee comes first: O(n log n) in the worst case. No luck, no assumptions; the merge does the same work whether the input arrived shuffled, sorted, or adversarial. The cost: the merge needs somewhere to write, so merge sort carries O(n) extra space, a scratch buffer the size of the input.

Two quieter properties do heavy lifting in production. The merge reads both halves front to back and writes front to back: three sequential streams, which lesson 2's prefetcher turns into raw bandwidth. And merging never needs random access, which makes merge sort the sort for data you can't index into. Linked lists: the Linux kernel sorts its lists with lib/list_sort.c, a merge sort. Data bigger than RAM: sort what fits, write sorted runs to disk, then merge the runs as streams. Every database that spills an ORDER BY to disk is running this lesson's merge step, and LSM-tree storage engines (RocksDB and friends) spend their lives merging sorted runs during compaction.

Quicksort: partition first

The second champion starts from the opposite end. Merge sort does all its work after the recursion, combining. Quicksort does all its work before. Pick an element, the pivot. Then partition: rearrange the array so everything smaller than the pivot sits to its left and everything bigger to its right. The pivot lands in its final sorted position, done forever. Recurse on the two sides. There is no combine step at all.

The partition scheme below is Lomuto's, chosen because it's the easiest to follow: it is literally lesson 7's reader/writer geometry, a reader scanning every element and a writer marking the end of the "smaller than pivot" zone. (Real implementations descend from Hoare's original 1961 scheme, which converges from both ends and does fewer swaps; same idea, more index bookkeeping.)

function partition(items, lo, hi):
    pivot = items[hi]                  # textbook pivot choice: see the catastrophe
    write = lo                         # boundary of the small zone
    for read from lo to hi-1:
        if items[read] < pivot:
            swap items[write], items[read]
            write += 1
    swap items[write], items[hi]       # pivot to its final slot
    return write

Walk it on [7, 2, 9, 4, 3, 8, 6, 5], pivot 5 (the last element):

One O(n) pass, in place, and 5 sits exactly where the final answer needs it. Recurse on [2, 4, 3] and [9, 8, 7, 6] and the base case finishes the job.

If pivots land near the middle, the analysis is merge sort's again: halve the problem, log n levels, n partition work per level, O(n log n), and a random pivot delivers that in expectation. And here's why quicksort wins benchmarks: no scratch buffer (the O(log n) expected stack is the only memory bill), no merge pass writing everything out and back, one hot loop comparing against a pivot that sits in a register while scanning forward through the array. Done well, quicksort is the fastest general-purpose comparison sort on real hardware.

Done well. Everything above leaned on three words: near the middle.

The catastrophe

Feed it the one input nobody expects to be dangerous: an array that's already sorted. [1, 2, 3, 4, 5, 6, 7, 8], pivot the last element, 8. The partition scans and everything is smaller, so the entire array lands in the small zone and the big zone is empty. The recursion gets everything except one element. Which pivots on 7, and peels off one more. Then 6.

Shrink by one per call. Lesson 9 named this the dangerous kind: depth n, not log n, so a hundred thousand already-sorted elements is a hundred thousand stack frames, a crash before it's even slow. And the comparisons sum to n + (n-1) + (n-2) + ...: the O(n²) triangle. The fast sort, handed the easiest possible input, degrades to the quadratic shelf and blows the stack on the way down. Sorted and nearly-sorted input is everywhere in production (yesterday's sorted file plus today's appends, a re-sort after one edit), so a sort that dies on sorted data cannot ship as-is.

Defending the pivot

Every production quicksort is a defense against that paragraph.

1. Random pivot. Don't be predictable. Pick the pivot uniformly at random and no fixed input is dangerous; the catastrophe now requires bad luck at every level, and the probability vanishes. Expected O(n log n) on any input.
2. Median of three. Look at the first, middle, and last elements; take the median. Sorted input now picks the true middle, a perfect pivot, and nearly-sorted input behaves.
3. Give up, on a timer. Musser's introsort (1997) runs quicksort while counting recursion depth. Past about 2 log n levels, the pivots have provably gone wrong, so it stops and hands the remaining mess to heapsort, a different O(n log n) sort that needs no luck (lesson 15 builds the heap; for now it's the insurance policy in the basement).

One more, because attackers read papers. Doug McIlroy's "A Killer Adversary for Quicksort" (1999) shows how to construct, on the fly, an input that drives a known quicksort implementation to near-worst-case behavior. Sorting attacker-supplied data with a predictable quicksort is a denial-of-service vector, the same genre of algorithmic-complexity attack as hash flooding. Randomize, or carry introsort's insurance; real libraries do both.

Stability, and why quicksort isn't

Time to pay off the word from the merge. A sort is stable if elements that compare equal keep their original relative order. Sounds like trivia; it decides library APIs. The concrete case: an employee table, sorted by name.

Now sort by department. Ana and Carla compare equal on department. A stable sort keeps Ana before Carla because she was before Carla coming in:

Two sorts composed into "grouped by department, alphabetical within each group", which is exactly what a human wants. An unstable sort may scramble names within each department, wasting the first sort entirely.

Grade the champions. Merge sort is stable for free: when the two pointers tie, the <= takes the left element first, preserving input order. Quicksort is not stable, and can't cheaply be made so: look back at the partition table, where the 7 jumped from slot 0 to slot 3 in one swap. Partitioning moves elements long distances, trampling the original order of equals. That single difference is why your language ships two sorts, and why the default is usually the stable one.

The n log n floor

Both champions landed on O(n log n). Coincidence? Could some undiscovered algorithm sort with comparisons in O(n)? No, and the argument fits in a paragraph.

Eight distinct elements can arrive in any of 8! = 40,320 orders, and a correct sort must handle all of them; each distinct arrival order requires a different set of moves to fix. The only information-gathering tool a comparison sort has is a yes/no question: is A less than B? One comparison can, at best, split the set of still-possible orderings in half. To pin down one ordering out of 40,320 takes at least log₂(40,320) ≈ 15.3, so 16 comparisons in the worst case, minimum, for any conceivable comparison sort. In general the bound is log₂(n!), which grows as n log n (Stirling's approximation makes it precise). That's the floor. It's why lesson 1's ladder calls O(n log n) "good sorting", full stop, not a waypoint.

One honest scope note: sorts that don't compare can beat the floor. Counting sort and radix sort exploit the structure of the keys themselves (small integers, fixed-width strings) and reach O(n) on the right data. They're outside this course's part 1; for comparison sorting, the plateau is the law.

How libraries actually sort

Now the payoff this course has been promising since lesson 1. Open the standard libraries and the first thing you learn is that nobody ships the textbook.

Timsort (2002). Tim Peters, a Python core developer, looked at what Python programs actually sort and noticed it's almost never random: logs are nearly sorted, files arrive in sorted chunks, someone appended to a sorted list. So he built a merge sort that exploits structure. Timsort scans for runs, stretches that are already sorted (descending runs get reversed in place). Runs shorter than the minimum (32 to 64 elements) are extended with, yes, insertion sort. Then it merges runs using a stack of pending merges with carefully chosen invariants, plus galloping: when one run keeps winning the comparison, switch from stepping to exponential jumps. On random data it's a solid stable n log n merge sort; on real-world data it approaches O(n), and fully sorted input is detected as a single run in one pass. It has been Python's list.sort for over twenty years, Java's Arrays.sort for objects since Java 7, and famously, in 2015, formal-verification researchers found a real bug in the run-stack invariant that could crash Java's version on pathological inputs; it was patched, and the episode is the best evidence that even twenty-year-old sort code is subtle.

Introsort and pdqsort (the quicksort family). C++ std::sort is Musser's introsort: quicksort with median-of-three-style pivots, the depth counter, heapsort insurance, and insertion sort below roughly 16 elements. Pattern-defeating quicksort (pdqsort, Orson Peters) is introsort with pattern detection added: already-sorted input runs in O(n), all-equal elements in O(n), and inputs that bend the pivots trip the fallback. Rust's sort_unstable shipped pdqsort (its current sorts are newer descendants of the same ideas), and Go adopted a pdqsort variant in the modern stdlib; Go's older sort.Sort interface API and the newer generic slices.Sort (stdlib since Go 1.21) run the same family, the generic one just pays less per comparison.

JavaScript got there last. Until 2018, V8 quicksorted any array longer than 10 elements, unstably, and a generation of frontend developers learned the word "stable" from bug reports about reordered table rows. V8 switched Array.prototype.sort to Timsort in 2018, and ES2019 made sort stability a spec requirement.

The summary table, what your language actually calls:

Squint at the table and every row makes the same three moves. A fast workhorse from the quicksort family, or a merge-family sort where stability is promised. Pattern detection, because production data has structure. And insertion sort at the bottom, every single time, for slices under a few dozen elements: lesson 1 planted that oddity, lesson 2 explained why it wins (two or three cache lines, slides inside L1), and here, finally, is where it lives. Inside every sort your code has ever called. The textbook algorithms are the skeleton; the engineering is everything wrapped around them.

The real code

The videos stay in pseudocode; here are both champions in the three languages this course carries, teaching versions with the load-bearing lines marked. Merge sort first.

function mergeSort(items: number[]): number[] {
  if (items.length <= 1) return items // base case
  const mid = Math.floor(items.length / 2)
  const left = mergeSort(items.slice(0, mid)) // the leap
  const right = mergeSort(items.slice(mid)) // of faith
  return merge(left, right)
}
 
function merge(left: number[], right: number[]): number[] {
  const out: number[] = []
  let i = 0
  let j = 0
  while (i < left.length && j < right.length) {
    // <= sends ties left, preserving input order: this character is stability
    if (left[i] <= right[j]) out.push(left[i++])
    else out.push(right[j++])
  }
  while (i < left.length) out.push(left[i++])
  while (j < right.length) out.push(right[j++])
  return out
}

func mergeSort(items []int) []int {
	if len(items) <= 1 {
		return items
	}
	mid := len(items) / 2
	left := mergeSort(items[:mid])
	right := mergeSort(items[mid:])
 
	out := make([]int, 0, len(items))
	i, j := 0, 0
	for i < len(left) && j < len(right) {
		if left[i] <= right[j] {
			out = append(out, left[i])
			i++
		} else {
			out = append(out, right[j])
			j++
		}
	}
	out = append(out, left[i:]...)
	return append(out, right[j:]...)
}

void merge_sort(std::vector<int>& items, std::vector<int>& scratch, int lo, int hi) {
    if (hi - lo <= 1) return;          // base case: zero or one element
    int mid = lo + (hi - lo) / 2;      // overflow-safe midpoint: lesson 8's famous bug
    merge_sort(items, scratch, lo, mid);
    merge_sort(items, scratch, mid, hi);
 
    int i = lo, j = mid, k = lo;
    while (i < mid && j < hi)
        scratch[k++] = (items[i] <= items[j]) ? items[i++] : items[j++];
    while (i < mid) scratch[k++] = items[i++];
    while (j < hi)  scratch[k++] = items[j++];
    std::copy(scratch.begin() + lo, scratch.begin() + hi, items.begin() + lo);
}

Read the TypeScript against the lesson. The base case and the two trusted calls are lesson 9's recipe verbatim. In merge, the while condition is the two-pointer budget from lesson 7 (each iteration advances exactly one pointer, so at most n iterations), and the <= on the comparison line is where stability lives; change it to < and ties go right, input order breaks, and no test on random numbers will ever catch it.

The Go version is the same skeleton; the slicing expressions items[:mid] and items[mid:] make the split free (slices share the underlying array, lesson 3), and pre-sizing out with make(..., 0, len(items)) avoids the grow-and-copy spikes from lesson 1's amortized section. The Go teaching version allocates a fresh buffer per merge; production merge sorts allocate one scratch buffer up front and reuse it all the way down, which is what the C++ version shows.

The C++ midpoint line deserves its beat: Joshua Bloch's 2006 post from lesson 8 was titled "Nearly All Binary Searches and Mergesorts are Broken", because the (lo + hi) / 2 overflow bug lives in this algorithm too. Same fix, same reason.

Now quicksort's partition, the Lomuto scheme from the walkthrough.

function partition(items: number[], lo: number, hi: number): number {
  const pivot = items[hi]
  let write = lo // boundary of the "smaller than pivot" zone
  for (let read = lo; read < hi; read++) {
    if (items[read] < pivot) {
      ;[items[write], items[read]] = [items[read], items[write]]
      write++
    }
  }
  ;[items[write], items[hi]] = [items[hi], items[write]]
  return write // the pivot's final, permanent index
}
 
function quickSort(items: number[], lo = 0, hi = items.length - 1): void {
  if (lo >= hi) return // base case: zero or one element
  const p = partition(items, lo, hi)
  quickSort(items, lo, p - 1)
  quickSort(items, p + 1, hi)
}

func partition(items []int, lo, hi int) int {
	p := lo + rand.IntN(hi-lo+1) // defense one: random pivot
	items[p], items[hi] = items[hi], items[p]
	pivot := items[hi]
	write := lo
	for read := lo; read < hi; read++ {
		if items[read] < pivot {
			items[write], items[read] = items[read], items[write]
			write++
		}
	}
	items[write], items[hi] = items[hi], items[write]
	return write
}

int partition(std::vector<int>& items, int lo, int hi) {
    int pivot = items[hi];
    int write = lo;
    for (int read = lo; read < hi; ++read)
        if (items[read] < pivot) std::swap(items[write++], items[read]);
    std::swap(items[write], items[hi]);
    return write;
}

The read and write variables are lesson 7's reader/writer pair by name. Note what's absent: no merge, no output array, no copying back. The two recursive calls share items and never touch each other's region, because the partition guaranteed the regions are independent. That guarantee is the whole algorithm.

The Go version builds in defense number one: the random index is swapped into the pivot slot first, then the partition proceeds unchanged. Two lines of defense, and the catastrophe is gone. Without those two lines this function is the one that dies on sorted input; with them, no fixed input can hurt it.

The strict < matters in all three: equal elements go right of the pivot, and either choice of side is fine for correctness, but no choice makes Lomuto stable; the long-distance std::swap is the order-trampling move from the stability section, visible in one line. And to be clear about what you'd actually ship: in production you call std::sort, slices.Sort, or .sort(), and now you know the machine you're invoking.

What's next

Sortedness is paid for, and the receipts are readable. Merge sort trusts both halves and earns everything in an O(n) merge: guaranteed n log n, stable, costs a buffer, sorts streams and lists and disks. Quicksort earns everything in an O(n) partition: in place, faster in practice, catastrophic without a defended pivot. The floor is n log n because comparisons only halve, and the libraries ship hybrids: pattern detection on top, insurance underneath, insertion sort in the small slices.

But look at what both champions actually did. Split the problem. Solve the pieces by recursion. Combine the results. Merge sort combines after, quicksort partitions before, and the arithmetic came out identical: log n levels, n work per level. That move is bigger than sorting. It has a name, divide and conquer, and a general theory that prices every algorithm shaped like this, including ones you haven't met yet: how to split, when it pays, and how to read the cost straight off the shape of the recursion. That's the next lesson.