Sorting

The searching lesson left an unpaid bill: binary search demanded sorted data, price quoted as O(n log n). This lesson pays it, and collects everything the level has taught along the way: nested-loop counting from the big-O lesson, recursion trees, merge sort's scratch space from the space lesson, even the BST's in-order traversal. Sorting is where the whole complexity toolkit performs in public, which is why every algorithms course, 6.006 included, uses it as the set piece.

The quadratic family: compare everything

The sorts humans perform by hand share one skeleton: repeatedly compare pairs and fix what is out of order. Selection sort scans the unsorted region for its minimum and swaps it into place, n scans of shrinking length. Insertion sort takes each new element and walks it backward into position among the already-sorted prefix, the card player's sort. Bubble sort swaps adjacent offenders until none remain. All three live inside two nested loops over the same data, and the big-O lesson taught you to price that shape on sight: the pair count is n times n minus 1, over 2, which is O(n^2) comparisons. At n equal to a million, that is roughly half a trillion comparisons, minutes to hours, for a task better algorithms finish in a blink.

Insertion sort deserves one kind word before the demolition: on data that is already nearly sorted, each element walks only a step or two backward, and the cost collapses toward O(n). Best case versus worst case again, and real engineering exploits it: the industrial sorts described at the end of this lesson hand small or nearly-ordered stretches to insertion sort on purpose.

Merge sort: divide, conquer, merge

Merge sort changes the shape of the work entirely, and it runs on the recursion lesson's engine. Split the array in half. Sort each half by the same method, recursion, with one-element arrays as the base case, already sorted. Then merge: two sorted halves zip together in one linear pass, repeatedly taking the smaller front element. The accounting is the famous recurrence: the work at each level of the recursion tree is O(n), all the merges at that depth touch each element once, and the tree is log n levels deep because halving n reaches 1 in log n steps. Total: O(n log n), every input, no luck involved. The visualizer below computes exactly that level-times-work product for n = 64, and lands on the same 384 the growth table showed back in the first lesson.

Merge sort's price tag, remembered from the space lesson, is O(n) auxiliary memory for the merge scratch array. Its rival at the top, quicksort, sorts in place: pick a pivot, partition smaller-left larger-right, recurse on the sides. Quicksort averages O(n log n) with excellent constants, but a consistently terrible pivot, always the smallest element, say, on sorted input with naive pivot choice, degrades it to O(n^2), the same sorted-input ambush that flattened the naive BST. Production quicksorts randomize or median-select pivots to make that worst case vanishingly unlikely, another echo of the hash lesson's move: use randomness you control to defend an average case. Heapsort, the third classic, pushes everything through the heap from the trees lesson for guaranteed O(n log n) in place, at constants that usually lose to the other two. Engineering picks among the three by which guarantee it values.

The floor: why n log n is the end of the road

Here is the most remarkable sentence in the level: no sorting algorithm that learns only by comparing elements can beat O(n log n) in the worst case, not now, not ever, on any hardware. The argument, given in Open Data Structures' sorting chapter, is pure information: n elements can arrive in any of n factorial orders, and the algorithm must do enough comparisons to distinguish which one it received. Each comparison has two outcomes, so k comparisons distinguish at most 2 to the k orders. Needing 2 to the k to reach n factorial forces k to be at least log of n factorial, which grows as n log n. That is an Omega bound, the lower-bound notation from the first lesson doing real work: merge sort and heapsort are not merely good, they are optimal for comparison sorting. The only escape is to stop comparing: counting and radix sorts exploit structure in the keys themselves, digits, bounded ranges, and reach O(n) for those special cases, stepping around the bound rather than breaking it.

Two practical footnotes: stability, and what ships

Stability is the property that equal elements keep their original relative order, and it matters the moment data has more than one field: sort orders by date, then stably by customer, and each customer's orders remain date-sorted, multi-key sorting by composition. Merge sort is naturally stable, take from the left half on ties, plain quicksort and heapsort are not. And what real runtimes ship is hybrids tuned with everything this level taught: Python and Java lean on Timsort, a merge sort that detects already-sorted runs and hands short stretches to insertion sort, exploiting its near-sorted best case. Other standard libraries use introsort, quicksort that watches its own recursion depth and switches to heapsort if an ambush pattern appears, a worst-case insurance policy written in complexity language. Reading those design notes is reading this lesson applied by professionals.

One more connection ties the level shut: the trees lesson noted that in-order traversal of a BST reads its keys sorted. Inserting n items into a balanced BST costs O(n log n), then one O(n) traversal reads them off sorted, sorting by data structure. It is not the fastest practical sort, but it shows the deep unity: search structures and sorting algorithms are the same halving idea, stored versus executed. Heapsort makes the same point with the heap.

Sorting and the analyst

In protection work, sorting appears on the attacker's bench more than the defender's. Analysts sort constantly: functions by size to find the VM dispatch loop, strings by entropy to find encrypted blobs, opcodes by frequency to fingerprint a custom instruction set, and the frequency-analysis pass an attacker runs over a virtualized program's bytecode begins with exactly the counting-and-ordering machinery of this lesson. That workflow runs in O(n log n), effectively free at any realistic program size, which carries a strategic moral: never assume an attacker cannot afford to organize your shipped bytes every possible way. They can, in seconds. What protection can control is whether the organized view says anything, which is why the serious techniques of Levels 5 and 6 aim to flatten the statistics themselves, uniform-looking constants, per-build instruction sets, rather than hoping disorder alone hides structure.

Nested-loop sorts cost O(n^2) pair comparisons; merge sort restructures the work into log n levels of linear merging for O(n log n) guaranteed, at O(n) scratch space. The information-theoretic lower bound proves comparison sorting can do no better, so merge sort and heapsort sit at the ceiling, and real runtimes ship hybrids that exploit best cases while insuring worst ones. Sorting is complexity analysis, performed.

Frequently asked questions