Field notes on putting things in order
Five comparison sorts, taken one step at a time, then run together at full speed.
Sorting an array means putting its elements into ascending order. The brute-force version — try every permutation, check each one — is correct and unusable: at twenty elements there are already 2.4 quintillion permutations. The practical sorts get the same answer by comparing pairs of elements and either swapping them or moving them around.
There is no best comparison sort. Which one is fastest depends on the input — its size, how shuffled it is, how many duplicate values, whether it's already nearly sorted or perfectly reversed. The five canonical sorts in this piece — bubble, insertion, mergesort, quicksort, heapsort — each handle those conditions differently, and the differences are most of why all five still exist. The first five sections take each one slowly, with a line of narration. The closing section runs all five against every input pattern at once, so the trade-offs become visible at a glance.
One readout to call out before we start: inversions left. An inversion is a pair of elements that are out of order relative to each other — a bigger one sitting in front of a smaller one, anywhere in the array. A sorted array has zero inversions; a perfectly reversed one has the maximum (n(n−1)/2). The number drops monotonically as any sort makes progress, regardless of which algorithm is doing the work, so it's a clean how close to done measure that doesn't favour any one approach.
A scanner that swaps when out of order
Walk the array left to right, comparing each adjacent pair. If they're out of order, swap them. Repeat. The thing being pushed forward by these swaps is always the largest element in the unsorted region — it bubbles to the right end of the pass and gets pinned there. One pass settles the rightmost slot, two passes settle the last two, n passes settle everything. Bubble sort is rarely the right tool, but it's the simplest one to draw.
The copper outline marks the pair under comparison. The gold tail on the right is the settled region.
Pick a card, slide it home
Insertion sort keeps a sorted prefix on the left. Each iteration takes the next unsorted element, lifts it out, and slides it backward over the prefix one comparison at a time, stopping when it hits an element smaller than itself. Drop into place; the prefix is one longer. This is what most people do when sorting a hand of cards.
The element floating above the strip is the one being inserted. The gold region on the left is the sorted prefix. Insertion sort runs in O(n²) on random input but is linear on already-sorted input — each new element only needs one comparison to confirm it's already in place.
Halve, then knit
Mergesort splits the array in half, sorts each half, and merges them. Two sorted strips can be combined into one sorted strip in linear time: walk both with a cursor, always emit the smaller of the two front elements, advance that cursor. The recursion bottoms out at length one, which is trivially sorted. The whole thing is O(n log n) regardless of input shape, and it costs O(n) auxiliary memory for the merge buffer.
The teal bracket above the strip marks the sub-array currently being merged; its vertical guides show the left and right boundaries. Three roles to track: the two copper-tinted bars are the front elements of the left and right halves being compared; the brass arrow is the write cursor, marking where the smaller of the two will be placed next. After each compare, one of the read cursors advances and the brass arrow moves one slot to the right.
Anchor and split
Pick a pivot. Sweep the rest of the array so everything ≤ the pivot ends up on its left and everything ≥ on its right. The pivot is now in its final slot, though neither side is sorted yet. Recurse on each side. Quicksort runs in place — no extra memory like mergesort — but its speed depends on the pivot. A pivot near the smallest or largest value barely shrinks the work, and the recursion can collapse to depth n.
Switch to the first pivot strategy and re-run a few times. The depth readout climbs toward n. Switch to median-of-3: it's almost always near the middle of the range, and the depth stays close to log₂(n). Production quicksorts use median-of-3 or one of its cousins for exactly this reason.
A tree that repeatedly gives up its largest
An array can be read as a binary tree without any extra storage: index 0 is the root, indices 1 and 2 are its children, indices 3–6 are the next level. Heapsort builds a max-heap (every parent ≥ both children) by sifting each non-leaf down once, bottom-up. The largest element is now at index 0. Swap it with the last unsorted slot, mark that slot settled, and sift the new root down through the shrinking heap. Repeat until the heap is empty. O(n log n), in place, no input-shape pathologies.
The tree above and the array below are the same data. Parent of i is ⌊(i−1)/2⌋; children of i are 2i+1 and 2i+2. Sift-down walks the active node downward through whichever child is larger until the heap property holds.
Same input, five characters
All five algorithms again, on 192 elements, lockstep so the operation counts are directly comparable. The shapes should be familiar from the small exhibits above — bubble's slow rightward creep, insertion's growing gold prefix, mergesort's level-by-level merging, quicksort's recursive split, heapsort's sift-and-extract rhythm — just at a scale where the asymptotic differences start to bite. Switch the input pattern to see each algorithm's character change.
Switch input patterns. On nearly-sorted, insertion finishes first by a wide margin. On reverse-sorted, mergesort and heapsort finish first. Bubble is slow on everything. Quicksort with median-of-3 holds up across all four patterns — its older "first pivot" sibling does not.
Where these algorithms came from
Bubble sort is folkloric — no clear inventor — and was already old by the time Kenneth Iverson formalised it in A Programming Language (1962). Donald Knuth, in volume 3 of The Art of Computer Programming, treats it mostly as a teaching foil.
Mergesort is older than electronic computers. John von Neumann described it in a 1945 internal report on the EDVAC, while reasoning about how to sort large data sets that wouldn't fit in primary storage — the same external-sort use case where mergesort still dominates today.
Quicksort came from Tony Hoare in 1959, while he was working at Moscow State University on a Russian-English machine translation project that needed to sort dictionary entries. He published it in 1961 in Communications of the ACM, and within a decade it was the default in-memory sort almost everywhere.
Heapsort is John W. J. Williams, also in the Communications of the ACM, 1964. Robert Floyd published the modern sift-down construction the same year, in the same journal, in two short notes that turned the heap into the data structure most working programmers know it as.
References
- Iverson, K.E. (1962). A Programming Language. Wiley.
- von Neumann, J. (1945). First Draft of a Report on the EDVAC. Internal report, Moore School of Electrical Engineering, University of Pennsylvania.
- Hoare, C.A.R. (1961). Algorithm 64: Quicksort. Communications of the ACM, 4(7), 321.
- Williams, J.W.J. (1964). Algorithm 232: Heapsort. Communications of the ACM, 7(6), 347–348.
- Floyd, R.W. (1964). Algorithm 245: Treesort 3. Communications of the ACM, 7(12), 701.
- Knuth, D.E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd ed. Addison-Wesley.