Sorting II: Heaps, Floors, and Clever Cheats
Last week ended with merge sort and quicksort both running at n log n, and a question hanging in the air: is that as good as sorting gets? This week answers it twice — once with a wall, once with a tunnel under the wall. Along the way we pick up a third n log n sort that runs a tournament inside the array, and then we collect the prize all this sorting has been for: finding things fast. Project 1 is due this week; §8 has your submission checklist.
The tournament bracket in §2 shows heapsort as what it really is: a bracket stored in a shelf, re-run every time the champion retires. The pigeonhole sorter in §4 sorts without a single comparison — watch its comparison counter stay frozen at zero. Drive both while you read; every number they show is computed live, not pre-written.
Session planHow we will spend the two sessions
Tuesday, Sep 29 — Session 8
Thursday, Oct 1 — Session 9
Section 1Where we left off
Last week you met three sorts and their personalities: insertion, unbeatable on nearly-sorted data; merge, steady at n log n with no bad days; quicksort, gambling on pivots and usually winning. Two of the three land on the same bill — n log n — and that is suspicious. When very different ideas keep hitting the same number, it starts to look less like coincidence and more like a law.
So this week runs on two questions:
- Can anything sort faster than n log n? The answer is the strangest "yes and no" in the course. No — for any sort that works by comparing items, n log n is a floor nothing can get under, and §3 shows you why with a picture. Yes — if you stop comparing altogether, and §4 shows two famous sorts that do exactly that.
- What is sorting for? Tidiness is not a use case. The honest answer is searching: a sorted list is a list you can find things in almost instantly, and §5 finally cashes that in.
But first, one more sorting algorithm — because merge sort left money on the table. It has no bad days, but it charges rent: a whole second array to merge into. Quicksort sorts in place, but it gambles. Is there a sort with merge sort's guarantee and quicksort's memory bill? There is, and it works like something you already understand from March basketball.
Section 2Heapsort: a tournament in the shelf
Think about how a tournament finds a champion. Players pair off; winners rise; after the final, one name sits at the top of the bracket. Here is the useful part: the bracket does not just crown the champion — it keeps its receipts. Every match already played is still written on the board. When the champion retires, you do not restart the whole tournament from scratch. You only re-run the matches along one path — the path the champion climbed — and a new champion emerges after just a handful of games.
That structure — everyone above beat everyone below them — is called a heap. And the trick that makes it an algorithm rather than a wall poster is this: the bracket is stored in a plain array. No boxes, no arrows, no extra memory. Slot 0 is the top of the bracket. The two players standing under slot 0 live in slots 1 and 2. The two under slot 1 live in slots 3 and 4; the two under slot 2 live in slots 5 and 6. In words: to find who stands under you, double your slot number and add one — that slot and its right-hand neighbor are your two challengers. The whole tree is an address scheme, not a data structure you have to build.
An array is a heap when every slot beats (is at least as big as) the two slots under it. That single local rule has a global consequence: the champion — the biggest value — is always in slot 0. Nothing else is promised: the second-biggest could be in slot 1 or 2, and the bottom row can be in any order. A heap is not sorted. It is exactly as organized as a bracket: certain about the champion, vague about everyone else.
Heaps have a much bigger life than sorting — they power priority queues, which run schedulers, event systems, and half the graph algorithms later this semester. That full story, alongside trees and balancing, is Week 7. Today we take only what sorting needs: the bracket rule, and one move.
The one move: re-running the bracket
Suppose the champion retires, and some ordinary player gets placed at the top of the bracket — a 6 standing where the 9 used to be. The bracket rule is now broken in exactly one place: the top. The repair is what a real tournament would do: re-run the matches on that one path. The 6 faces its two challengers; the stronger challenger wins the slot and the 6 drops down a level. It faces its two new challengers; same thing. It keeps sinking until it beats both players under it — or hits the bottom row. This move is called sift-down, and it is heapsort's entire engine room.
Heapsort: build the bracket, pull champions
Now the whole algorithm fits in two sentences. First, turn the messy array into a bracket: walk the parents from the bottom row upward and sift each one down, so that by the time you fix a slot, everything under it is already a proper bracket. Then pull champions: swap the champion at slot 0 into the last slot — its final resting place — shrink the bracket by one so that slot is out of the game, and sift the newcomer at the top back down. Repeat. Each pull parks the next-biggest value at the end, so the sorted region grows from the right while the bracket shrinks from the left — inside the same array. No second array, ever.
And the bill, in plain words: n champions get pulled, and each pull costs one bracket re-run — about log n matches. That is n log n, the same as merge sort, with quicksort's memory bill: zero extra. Building the bracket at the start sounds like it should cost extra, but it is actually the cheap part — most of the parents you fix are in the bottom rows, where the brackets under them are only a level or two tall, so most of those sift-downs end after a match or two.
Watch it happen. The bracket and the shelf below it are the same array — every swap moves both views at once.
Almost nothing — and that is the design. You know exactly one global fact: the biggest value is in slot 0. Everything else is only locally promised (each slot beats the two under it), which allows wildly unsorted arrangements — run the demo and look at the bottom row right after the build. A heap is deliberately under-organized: the least work that still keeps the champion instantly findable. The sorting happens later, one champion at a time.
So why does anyone use merge sort or quicksort, if heapsort has both virtues?
Constants and memory patterns, not big-O. Sift-down hops around the array while quicksort's partition strides through it left to right — and real machines fetch memory in neighborhoods, so striding is much cheaper per step. It is the same "theory vs the machine" gap your Project 1 report reconciles. Heapsort is the dependable second choice: what you reach for when you need a guaranteed n log n, in place.
Section 3The floor: why n log n is the wall
Three different sorts — merge, quick, heap — three different ideas, one bill: n log n. Time to explain why, and the explanation is one of the prettiest arguments in the course. It does not examine any algorithm. It counts answers.
Play twenty questions with me. I am thinking of one thing out of a big collection; you ask yes/no questions. Here is the iron rule of that game: k yes/no questions can tell apart at most 2k things. One question splits the world into two piles; a second question splits each pile again, giving four; then eight, sixteen, and so on. If my collection has more things than your questions have answer-patterns, then two different things must produce the same pattern of answers — and you cannot tell them apart. No cleverness fixes this. It is not about strategy; it is about how many leaves a tree of yes/no branches can have.
Now the trap springs. When a sorting algorithm compares two items — "is a smaller than b?" — it is asking a yes/no question. And what is it trying to figure out? Which of the possible orderings of the input it was handed. Three items can arrive in 6 different orders. Four items: 24. Five: 120. Each new item multiplies the count by its position number, so the number of orderings explodes fast — for n items it is written n! and pronounced "n factorial," and for even 20 items it is already past two quintillion.
Here is why you should believe the general claim, in the same three-item spirit. A sort must be able to end at any of the n! orderings, and each one needs its own leaf in the question tree. A tree k questions deep has at most 2k leaves — so the worst-case number of comparisons must be at least the number of doublings it takes to reach n!. And n! is so enormous that reaching it takes about n log n doublings. That is the whole calculation. The floor is n log n, and merge sort and heapsort are standing on it — within a whisker of the best any comparing sort can ever be, including ones nobody has invented yet.
The argument counted comparisons — questions of the form "is this smaller than that?" It says nothing about algorithms that never ask such questions. That is not a loophole we are inventing to feel better; it is a genuine gap in the theorem, and the next section drives two famous algorithms straight through it.
Count answers, not steps. Four items can arrive in 4! = 24 different orders, and each order needs its own leaf in the question tree. But 4 yes/no questions produce at most 2 × 2 × 2 × 2 = 16 answer-patterns — fewer than 24. So two different orderings must produce the exact same answers, and the algorithm will handle at least one of them wrongly. Notice what you never needed: the algorithm itself. That is a lower bound's power — it convicts every algorithm at once, including the uninvented ones. (Five comparisons gives 32 ≥ 24, and a 5-comparison sort of 4 items really exists.)
Section 4Cheating honestly: sorting without comparing
Picture a professor with 300 exam papers, each marked with a score from 0 to 100, who wants them in score order. Does she compare papers two at a time, merge-sort style? Of course not. She sets up pigeonholes labeled 0 through 100, walks the stack once, dropping each paper straight into the hole matching its score — then walks the shelf once, left to right, scooping the holes into one pile. Done — perfectly sorted.
Stop and check what just happened against §3. No paper was ever compared with another paper. No yes/no questions were asked — the score itself is the address, and the paper teleports directly to where it belongs. The twenty-questions argument has nothing to grab onto, and the bill shows it: one pass over the n papers, one pass over the k pigeonholes — about n + k work, plain and linear. This is counting sort, and it is not breaking the law of §3. It is refusing to play the game the law is about.
The catch, and the second cheat
Why don't we counting-sort everything, then? Look at what the trick quietly required: a small, known menu of possible values. Scores 0–100? 101 holes, lovely. Nine-digit ID numbers? A billion pigeonholes, almost all empty — the shelf costs more than the sorting. Arbitrary decimals, or names? No finite shelf exists at all. Counting sort is a specialist: devastating inside its niche, useless one step outside it.
The second cheat rescues part of that. Long before computers, librarians sorted thousands of numbered index cards with only ten pigeonholes — one per digit, 0 through 9. The trick: sort the cards one digit at a time, and — the famous surprise — last digit first. Deal the cards into the ten holes by their final digit and scoop; re-deal by the middle digit and scoop; then by the first digit and scoop. After the final scoop the cards are fully sorted. This is radix sort — "radix" is just an old word for the base of the number system, our familiar ten.
Why does last-digit-first work? Because each dealing pass is stable: cards land in a hole in the order they arrive, so ties keep their existing order (stability was a footnote to merge sort's <= last week; here it becomes the load-bearing wall). The most important digit gets the final pass, so it has the final say — and among cards that agree on it, stability preserves every decision the earlier passes already made. Watch for the moment in the demo's last pass when cards sharing a leading digit slide into a hole already in order.
The bill: for numbers of d digits, radix sort makes d passes, each costing about n + 10. Three-digit numbers: three cheap linear passes. That is why it shows up anywhere the keys are fixed-width — ID numbers, dates, zip codes, network addresses — and why it, too, is a specialist: hand it free-form data with no digit structure and it has nothing to grab.
First-digit pass: hole 1 gets 14, 11; hole 4 gets 41, 44 — scoop: 14, 11, 41, 44. Last-digit pass: hole 1 gets 41, 11; hole 4 gets 14, 44 — scoop: 41, 11, 14, 44. Wrong, because the second pass shuffled cards across the tens-groups the first pass had carefully built, destroying that work. Last-digit-first never has this problem: the most important digit gets the final say, and each pass only rearranges within what stability preserves from before. The rule of thumb: sort by the least important key first, so the most important decision is made last and nothing can overturn it. (You will use exactly this to sort records by several fields at once.)
Section 5Searching: what all this sorting buys
Two weeks of sorting — time to collect. The claim from the very start of Notes 04 was that sorted data is a superpower, and the superpower has a name: finding things.
On an unsorted shelf of n items there is only one honest strategy: the linear scan. Start at one end, check everything, stop when you find it — or reach the far end to learn it was never there. Average bill, half the shelf; worst case, all of it. Nothing clever survives unsorted data, because where one item sits tells you nothing about where any other might be.
On a sorted shelf, everything changes — you saw the picture in Notes 04's first figure, four hops finding 47 on a fifteen-slot shelf. One look at the middle kills half the shelf; the next kills half of what is left. That is binary search, the halving trick you have carried since Notes 02, and its bill is the halving count itself: about log n looks — 20 for a million items, 30 for a billion. Doubling the data adds one look. This is the payoff line of the fortnight: sorting costs n log n once, and turns every future search from n into log n. Sort once, harvest forever.
Can you beat even binary search? Sometimes — by searching the way you actually use a dictionary. Nobody looks up "zebra" by opening to the exact middle; you open near the back, because you know z lives there. That is interpolation search: estimate where the target ought to sit from its value, and jump straight to that neighborhood. On smoothly spread data the number of looks barely grows at all as n explodes; on lumpy data its guesses mislead it, and it can limp home slower than plain halving. A personality, like the sorts: brilliant on the right data, fragile off it.
There is one more search, and it is the counting-sort idea wearing a different coat: what if the item's value could tell you its shelf position directly, no probing at all — like a coat-check ticket that names its own hook? Making that work for arbitrary data (not just tidy 0-to-100 scores) is hashing, it averages out near one look per search, and it is all of Notes 06. It also runs Python's dict and set, so you have been using it all along.
For a single search, sorting first is a terrible deal: the sort costs n log n — about twenty million operations — to save at most one million, a scan's worth. The honest rule is arithmetic, not slogans: sorting pays for itself once (searches × savings) outgrows the one-time n log n fee — usually after a couple of dozen searches. One search: scan. A search-heavy life: sort once — or wait for next week's hash tables and skip the whole question.
Section 6The map of sorting
Six sorts in two weeks. Here is the whole territory on one honest table — worth more than any paragraph in these notes, and exactly the kind of judgment call Project 1's write-up asks you to defend with your own measurements.
| Sort | Typical bill | Worst day | In place? | Reach for it when… |
|---|---|---|---|---|
| Insertion | n² | n² | yes | the list is tiny or already nearly sorted — there it beats everything below |
| Merge | n log n | n log n | no — needs a second array | you want a guarantee plus stability, or data you cannot jump around in |
| Quick | n log n | n² — made astronomically rare by a random pivot | yes | big shuffled data in memory and you want raw speed |
| Heap | n log n | n log n | yes | you need the guarantee and can't afford merge sort's extra array |
| Counting | n + k (k = size of the value menu) | n + k | no — needs the holes | keys come from a small known menu: scores, ages, small codes |
| Radix | d passes of n + 10 (d = digits per key) | same | no — needs the holes | lots of fixed-width keys: IDs, dates, zip codes |
Read the table as a decision, top to bottom: Do the keys have a small menu or fixed digits? Cheat — the floor does not apply to you. If you must compare: nearly sorted or tiny, insertion; need certainty, merge or heap depending on whether you can spare the memory; otherwise, randomized quicksort. And remember from last week that the sort you will actually call, sorted(), is Timsort — merge and insertion combined by someone who had internalized this exact table.
Section 7The code
This week's algorithms in Python, written to be read next to their sections. The heapsort comments speak bracket, on purpose — if a line stops making sense, re-run Demonstration 1 until it does.
Heapsort
def sift_down(a, top, size): """Re-run the bracket below slot `top`. Assumes everything under `top` already obeys the bracket rule; afterward the whole region down from `top` obeys it again. """ while True: left = 2 * top + 1 # the two challengers under this slot: right = 2 * top + 2 # double-and-add-one, and its neighbor best = top if left < size and a[left] > a[best]: best = left # left challenger is winning the match if right < size and a[right] > a[best]: best = right # no — the right one is if best == top: return # slot-holder beats both: bracket restored a[top], a[best] = a[best], a[top] # loser drops down one round… top = best # …and must defend its new slot def heapsort(a): """Sort the list a in place, smallest first, and return it.""" n = len(a) # 1 · build the bracket: fix every parent, bottom row upward, # so each sift-down lands on already-valid sub-brackets for i in range(n // 2 - 1, -1, -1): sift_down(a, i, n) # 2 · pull champions: the biggest sits at slot 0 every time for end in range(n - 1, 0, -1): a[0], a[end] = a[end], a[0] # champion retires to the shelf's end sift_down(a, 0, end) # re-run the bracket, one slot smaller return a
Notice size doing quiet double duty: it is how the bracket "shrinks" without moving anything. The retired champions past end are still in the array — sift-down simply refuses to look at them. One array, two regions, zero extra memory.
Counting sort
def counting_sort(a, biggest): """Sort whole numbers between 0 and `biggest`. Returns a new list. No comparisons anywhere — the value is the address. Worth it only when `biggest` is modest (see the catch, §4). """ holes = [0] * (biggest + 1) # one pigeonhole per possible value for x in a: holes[x] += 1 # drop each paper straight into its hole out = [] for value in range(biggest + 1): # walk the shelf left to right… out.extend([value] * holes[value]) # …scooping every hole in order return out
Two loops, no nesting, and the first thing to notice is what is missing: there is no if x < y anywhere. Nothing in this function ever asks which of two elements is bigger. And to close the fortnight where it started — once any of these sorts has run, the three-line binary search you wrote back in Notes 02 (mid, keep the live half, repeat) is finally allowed onto the shelf, and a million-item lookup drops to twenty looks.
Section 8Before next session
You have been building this for three weeks; this is just the wrap-up, not a sprint. Before you submit, walk this list once, calmly:
- Code complete and honest: your sorting and searching implementations plus the benchmark harness, running from a clean clone. A README that says how to run everything is part of "complete."
- Tests pass — including the unglamorous inputs: empty list, one element, duplicates, already sorted, reversed. (Notes 01 told you every clause you skip is a bug you authorized; this is where that gets graded.)
- The write-up does its real job: measured curves next to predicted ones, and a straight-faced explanation of every place they disagree. Disagreements are not mistakes — unexplained disagreements are.
- Submit both pieces via Brightspace: the link to your Git repository and the report. Check that the repo is accessible to me and that your final commit is actually pushed.
If something breaks at the last minute, email me before the deadline, not after — problems become unrecoverable only by going quiet about them. You have done the hard part already; land it.
- Review these notes, and drive both demonstrations. Pull all seven champions in the tournament; run the pigeonhole sorter in both modes and watch the comparison counter not move.
- Two-sentence exercise, bring it Tuesday: one real dataset where you would cheat (counting or radix) and why the cheat applies; one where you could not possibly, and which comparison sort you would pick for it instead.
Next week we take the coat-check idea from §5 seriously: hash tables — how Python's dict finds anything in about one look, what a collision is, and what "amortized cost" means when the magic occasionally stalls. That is Notes 06, and it is also the heart of Project 2.