42Sorting, properly — and a beautiful impossibility

In Chapter 41 we let a function call itself and walk a whole tree of choices to find an answer. This chapter asks a colder, sharper question about code you already own. Not how a sort works, but whether it can be beaten. You stepped the five classic sorts line by line in the trace walkthroughs and raced them in the Algorithms Lab. So we skip the how and go straight at the wall, the hard floor every one of them slams into. Then we meet the one trick that strolls clean through it. The whole way, we keep circling the question that turns a coder into a computer scientist. Is n log n the best any sort can do, or just the best we've thought of so far? By the end you'll be able to prove, on the back of a napkin, that no sort built from comparisons can ever beat n log n. And then you'll sort a million items in a single linear pass, under that limit, by refusing to compare at all.

01The five sorts share one hidden move

Let's start by lining them all up. Bubble, selection, insertion are the three O(n²) sorts that crawl once the list gets big. Merge and quicksort are the two O(n log n) sorts that win at scale. Five different dances, and the Lab lets you watch each one shuffle the bars into place. But squint at any of them and the same atomic move keeps flashing past: pick two items, ask which is bigger, act on the answer. The swaps, the splits, and the merges are just bookkeeping wrapped around that one question.

That shared move is the key to the whole chapter, so hold onto it. Suppose the only thing your algorithm can ever learn about the data is the outcome of a < b questions. Then the number of questions is the true cost of the sort. And there is a hard floor on how few questions you can get away with. Call any algorithm that lives by this rule a comparison sort. All five of yours are comparison sorts, and so is almost every sort you have ever seen.

Before the proof, play a quick game with me. I pick a secret number between 1 and 1000, and you ask only yes/no questions. Ten questions are always enough, because each answer can cut the survivors in half. Ten halvings turn 1000 candidates into one, since 2¹⁰ = 1024 is just past 1000. And nine questions can never be enough. Nine answers have only 2⁹ = 512 possible patterns, and 512 patterns cannot point at 1000 different numbers. Twenty questions, the party game, is the same mathematics, since 2²⁰ is just over a million. Hold that shape in your head. A sort is playing the same game, except the secret is not a number but the input's hidden arrangement, and every a < b is one yes/no question.

02The speed limit — and why nobody can break it

Here is the most beautiful argument in this volume, and it is pure counting. Lay out every decision your sort could possibly make, drawn as one big tree. At the top sits the first comparison the algorithm performs. Two branches, yes and no, lead down to the next comparison, which depends on the answer. Keep going until the sort has nothing left to ask, and the picture you get is a decision tree. Internal nodes are comparisons, each edge is an answer, and every path from the top down is one possible run of the algorithm on some input.

Where does a path end? It ends at a leaf — the moment the sort stops asking questions and commits to one final output order. Now the punch line, and it is pure multiplication. A list of n distinct items has n! possible starting arrangements: n choices for the first slot, n−1 for the second, and so on down to the last. Each arrangement needs its own different reshuffle to come out sorted. So the tree must have at least n! leaves, one distinct verdict for every arrangement it might be handed. Miss even one leaf and somewhere out there sits an input your sort gets wrong, every single time.

Make it tiny and it stops being abstract. Take three songs, Levels, Titanium, and Starboy, so n = 3 and there are 3! = 6 possible shuffles of the playlist. Now try to sort them with only two comparisons. Two yes/no answers can produce at most 2 × 2 = 4 distinct paths, which means at most 4 leaves. But we need 6 different verdicts, and 4 slots cannot hold 6 answers. So two comparisons must fail on some shuffle, no matter how cleverly you choose them. Three comparisons give 2³ = 8 leaves, and 8 is finally enough room for 6. That is the whole proof, played on a toy.

Now weigh the tree. Each comparison you answer drops you exactly one level, so the height of the tree, its longest root-to-leaf path, is the worst-case number of comparisons. And a binary yes/no tree of height h can hold at most 2ʰ leaves, because the room only doubles as you descend. There are 2 slots at depth 1 and 4 at depth 2, doubling each level. Put the two facts together:

Read what just happened, because it is bigger than it looks. We never named a specific algorithm anywhere in the argument. Whatever your comparison sort is, it is some decision tree. That covers the ones you know, the ones you will invent, and the ones no human has thought of yet. And every decision tree that sorts n items must stand at least log₂(n!) levels tall. That is why n log n is not "the best we have managed" but the best that can exist. Merge sort already sits on that floor, which means you cannot pay less.

One symbol deserves demystifying before we lean on it any harder. log₂(x) answers a plain question: how many doublings does it take to reach x? Doubling ten times gives 1024, so log₂(1024) = 10, and read backwards it counts halvings instead. That is exactly why it shows up in a bound about yes/no questions. Each comparison, at its very best, halves the set of arrangements still consistent with every answer so far. Start with n! suspects and you need log₂(n!) halvings to corner the last one standing. The logarithm is not decoration, because no yes/no question can ever do better than halve.

Grind one out yourself before you trust the table coming up. Take n = 4 items, which have 4! = 24 possible arrangements, so the tree needs 24 leaves. A yes/no tree four levels tall holds only 2⁴ = 16 leaves — too few, so four comparisons cannot always sort four items. Go one level deeper and 2⁵ = 32 leaves is finally enough room for 24. So the floor for four items is 5 comparisons, and notice it sits neatly between the 3 we found for three songs and the 7 the next paragraph reports for five.

The numbers are concrete, and I checked each one in Python. To sort 3 items you need at least ⌈log₂ 6⌉ = 3 comparisons. For 5 items the floor is 7, for 12 items it is 29, and for 100 items it is 525. And log₂(n!) hugs n log₂ n so tightly that by a million items the floor is already 93% of it. It is the same curve and the same Θ(n log n) band, forever.

The floor only holds if you insist on comparing. What if the values could tell you where they belong — without a single comparison? →

03Walk through the wall — counting sort

Suppose you are sorting a million song ratings, each an integer from 0 to 5. The comparison floor says n log₂ n ≈ 20 million questions. But you never need a question. A rating of 5 doesn't need to be compared with anything — it just is a 5, and you already know exactly where all the 5s go: after the 4s, before nothing. The value is its own address.

That is counting sort. Make one tally box for each possible value. Walk the data once, dropping each item into the box that matches it. Then walk the boxes in order and pour them back out. No item is ever weighed against another. Here it is, and it really runs:

def counting_sort(a, k):        # every value is an int in range 0..k-1
    count = [0] * k             # one tally box per possible value
    for x in a:                 # PASS 1 - n steps: tally each item
        count[x] += 1           #   the value IS the index. no comparison.
    out = []
    for v in range(k):          # PASS 2 - k steps: walk boxes in order
        out.extend([v] * count[v])   # pour box v back out, count[v] times
    return out

print(counting_sort([3,1,4,1,5,9,2,6,5,3,5,0,7,2,6], 10))
# [0, 1, 1, 2, 2, 3, 3, 4, 5, 5, 5, 6, 6, 7, 9]   <- matches sorted()

Let's read it line by line. count = [0]*k builds k empty boxes, one for each possible value. The first loop runs n times, and inside it count[x] += 1 uses the value x directly as an array index. Volume 1 told us why that is cheap: indexing a list is O(1), a straight jump to a memory address. The second loop runs k times, emitting each value as many times as it was tallied. Total work: n + k. I ran it against Python's sorted() on the same data, and the result was identical output.

Trace it on something you can hold in your head. Take five ratings, [3, 5, 1, 3, 0], with k = 6 possible values from 0 to 5. After the tally loop the boxes read [1, 1, 0, 2, 0, 1]: one 0, one 1, no 2s, two 3s, no 4s, one 5. Now pour the boxes out in index order and you get [0, 1, 3, 3, 5]. Check it against your own eyes — that is the five ratings, sorted, and no two ratings were ever compared. The order came entirely from where each value landed, because the value is the index.

When k is small next to n, this is linear, and it strolls under the comparison floor like the floor isn't there. I measured the op counts on real data. A million items with values in 0–255 costs about 1,000,256 steps, where a comparison sort would spend ~20 million. That is roughly 20× fewer operations for the exact same result. And there is no contradiction with the last section. The floor was proven for sorts that only compare, and counting sort never compares — different game, different rules.

One quiet limitation, because it sets up the next section. The counting sort we just wrote throws the items away and rebuilds them from the tally — fine when a rating is just the number 5, but useless when each item is a whole record, a song and its rating. The fix is small: make each box a list instead of a bare counter, and append each record as you meet it. Walk the input front to back and equal keys land in their arrival order, because you only ever append, never reorder. That property has a name, stability, and radix sort in the next section leans on it completely.

The price is written right into the method. You need k boxes, so the values must be bounded integers, or things you can map onto a small integer range. You cannot counting-sort arbitrary floats or strings this way. You also pay O(k) memory for the boxes themselves. Push k up toward "any 64-bit integer" and you would need billions of boxes, and the trick collapses. Counting sort wins precisely when the range of values is small, whatever the count.

Bounded to 0–5 is easy. But a million distinct 9-digit ID numbers? That is k = a billion boxes. There is a way to keep the linear speed anyway — sort them one digit at a time. →

04Radix sort — counting, one digit at a time

Big numbers break counting sort because their range is huge. But look at each individual digit and the range is tiny again, just 0 to 9. So here is the move. Sort the whole list by the last digit, then by the next digit, working up to the first, using a stable counting sort on every pass. After the final digit the whole list comes out sorted, every number in its place. This is radix sort, and it is exactly how the old punched-card machines physically sorted — a fact we'll come back to.

Watch it happen on five real numbers: [531, 425, 519, 340, 923]. The first pass sorts by the ones digit only, giving [340, 531, 923, 425, 519]. The second pass sorts by the tens digit and produces [519, 923, 425, 531, 340], and notice one detail there. 923 and 425 both have tens digit 2, and the stable pass kept 923 first, exactly the order the previous pass left them in. The last pass sorts by the hundreds digit: [340, 425, 519, 531, 923], fully sorted. The tie at hundreds digit 5 resolved itself, because 519 already sat before 531 from the earlier passes. The early passes settle the small digits, and stability carries that work forward untouched.

That last-digit-first order isn't a modern invention — it's how the machines that ran the 1890 US census physically sorted. Herman Hollerith's tabulators read punched cards, one column of digits at a time. A mechanical reader dropped each card into one of ten bins, 0 through 9, by the digit punched in that column. An operator gathered the bins back up in order, then ran the whole deck again on the next column, least significant first — exactly our passes. And because the cards kept their stacking order inside each bin, the sort came out stable for free. Radix sort is that card machine, written in software.

def radix_sort(a):
    m = max(a)
    exp = 1
    while m // exp > 0:              # one pass per digit of the biggest number
        a = counting_by_digit(a, exp)   # stable counting sort on this digit
        exp *= 10                    # move to the next digit up
    return a

print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]   <- matches sorted()

Count the cost. The loop runs once per digit, call that d passes, and each pass is a counting sort over ten boxes costing O(n + 10). Total: O(d·(n + 10)), which for fixed-width keys is just O(n). I ran it against sorted() and the outputs match. But the whole thing works only because each pass is stable, which means it never disturbs the order the earlier passes established. That word, stable, is doing enormous quiet work here, and it deserves its own section next.

Everything in radix hangs on one promise: equal-keyed items keep their order across passes. Break that promise and the whole scheme scrambles. Time to make it precise. →

05Stability — when equal keys must keep their order

A sort is stable if, when two items compare equal on the sort key, they come out in the same order they went in. Unstable sorts are free to shuffle ties. It sounds like a technicality. It is the difference between a spreadsheet that does what you meant and one that quietly corrupts your data.

Why it matters: it is how you sort by two keys. Say you want your playlist grouped by artist, and within each artist, ordered by length. Sort by the secondary key first (length), then by the primary key (artist) with a stable sort — the stable pass keeps the length-order intact inside each artist group. I ran exactly this:

songs = [("Levels","Avicii",200), ("Wake Me Up","Avicii",247),
         ("Titanium","Guetta",245), ("Without You","Guetta",210),
         ("Hey Brother","Avicii",254)]

step1 = sorted(songs, key=lambda s: s[2])   # first by seconds (secondary key)
step2 = sorted(step1, key=lambda s: s[1])   # then by artist (primary), STABLE

# ('Levels','Avicii',200) ('Wake Me Up','Avicii',247) ('Hey Brother','Avicii',254)
# ('Without You','Guetta',210) ('Titanium','Guetta',245)

Read the result carefully, because the magic is in the ties. The Avicii block is internally sorted by seconds (200, 247, 254), and the Guetta block too (210, 245). Yet the second sort only ever looked at the artist name. The stable pass never touched the ties, so the first sort's work survived underneath it. Two stable sorts in a row give you a two-level ordering, for free. An unstable sort would have jumbled the seconds within each artist, and you'd be forced to sort with a compound key instead.

import random
from operator import itemgetter


def insertion_sort(a):
    """In place. Lift a key out, slide bigger items right, drop it in."""
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:      # STRICTLY greater -> stable
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a


print(insertion_sort([5, 2, 4, 1, 3]))
print(insertion_sort([]), insertion_sort([7]), insertion_sort([2, 2, 1]))

random.seed(42)
for n in (0, 1, 2, 50, 400):
    xs = [random.randint(0, 99) for _ in range(n)]
    assert insertion_sort(xs[:]) == sorted(xs), n
print("insertion_sort matches sorted() on 5 sizes: True")


tracks = [("Titanium", "Sia", 245),
          ("Chandelier", "Sia", 216),
          ("Blinding Lights", "The Weeknd", 200),
          ("Elastic Heart", "Sia", 250),
          ("Save Your Tears", "The Weeknd", 215),
          ("Levitating", "Dua Lipa", 203)]

step1 = sorted(tracks, key=itemgetter(2), reverse=True)   # SECONDARY first
step2 = sorted(step1, key=itemgetter(1))                  # PRIMARY last
for name, artist, secs in step2:
    print(f"{artist:<11} {secs:>4}  {name}")
print(step2 == sorted(tracks, key=lambda t: (t[1], -t[2])))

wrong = sorted(sorted(tracks, key=itemgetter(1)), key=itemgetter(2), reverse=True)
print([(t[1], t[2]) for t in wrong])


# ---------- the actual run, python 3.12.7 ----------
#
# [1, 2, 3, 4, 5]
# [] [7] [1, 2, 2]
# insertion_sort matches sorted() on 5 sizes: True
# Dua Lipa     203  Levitating
# Sia          250  Elastic Heart
# Sia          245  Titanium
# Sia          216  Chandelier
# The Weeknd   215  Save Your Tears
# The Weeknd   200  Blinding Lights
# True
# [('Sia', 250), ('Sia', 245), ('Sia', 216), ('The Weeknd', 215), ('Dua Lipa', 203), ('The Weeknd', 200)]
#
#
# ---------- reading it ----------
#
# 1. WHY '>' AND NOT '>='.
#    With '>', a key stops the moment it meets an equal item and lands to
#    its RIGHT -- so equal items keep their original relative order. That
#    is stability, and it is the entire second half of this exercise.
#    With '>=', an equal item is treated as "bigger", gets shifted right,
#    and the key overtakes it -- equal items come out reversed.
#    For a list of plain ints you cannot see the difference: 2 and 2 are
#    indistinguishable, and [1, 2, 2] prints the same either way. The data
#    that notices is data with a PAYLOAD -- (title, artist, seconds) rows,
#    records, objects -- where two items compare equal on the key and still
#    differ in every other field. One character, and the two-pass trick
#    below stops working.
#
# 2. WHICH PASS GOES FIRST.
#    The LAST sort you run is the PRIMARY key. So: sort by seconds
#    descending FIRST, then by artist. The artist pass is stable, so
#    inside each artist block the seconds order laid down by pass 1
#    survives untouched. Read it as a rule: sort by the least significant
#    key first and the most significant key last -- which is exactly what
#    radix sort does in section 04, one digit at a time.
#
# 3. THE PROOF.
#    step2 == sorted(tracks, key=lambda t: (t[1], -t[2])) prints True.
#    Two independent stable passes give bit-for-bit the same list as one
#    compound key. That equality IS the definition of stability, made
#    executable.
#
# 4. THE WRONG ORDER, SEEN.
#    Sorting by artist first and seconds second gives
#       Sia 250, Sia 245, Sia 216, The Weeknd 215, Dua Lipa 203, Weeknd 200
#    -- The Weeknd is split in half by Dua Lipa. The artist pass did happen;
#    the seconds pass simply overwrote it, because the last sort wins. The
#    result is not "a bit off": the grouping you asked for is gone.
#
# 5. WHY YOU WOULD EVER DO THIS IN TWO PASSES.
#    Because -t[2] only exists for numbers. When the secondary key is text
#    you want descending, there is no unary minus to reach for, and
#    reverse= applies to the WHOLE key, not one field of it. Two stable
#    passes handle mixed directions that a single compound key cannot
#    express -- and each pass reads as one plain sentence.

Python's sorted() is stable, and I have been leaning on that all chapter. But what is sorted()? It isn't plain merge sort. It is something cleverer — and it gets suspiciously fast on data that is already a bit sorted. →

06What sorted() actually runs — Timsort

Real data is rarely random. Logs arrive almost in time order, a list you append to and re-sort is mostly sorted already, and sensor readings drift slowly. Timsort, the algorithm behind Python's list.sort() and sorted(), is built around that one observation. It is a merge sort / insertion sort hybrid. First it scans the list for runs, stretches that are already in order. Every run it finds is work it doesn't have to do. Then it merges the runs together, using insertion sort to tidy the short pieces and clever "galloping" to skip through the long ones.

That word galloping deserves a second, because it's the trick that makes long runs cheap. A plain merge compares the fronts of the two runs and takes the smaller, one item at a time. But suppose one run keeps winning, again and again — its values are all smaller for a long stretch. Galloping notices the streak and stops crawling. It binary-searches ahead into the winning run to find where the other run's front item would finally slot in, then copies that whole block in a single move. Dozens of one-by-one comparisons collapse into one jump. On data with long ordered stretches, that is most of the merge skipped outright.

You can see runs without running any code at all. Look at the list [10, 20, 30, 3, 2, 1, 15, 25] for a moment. Timsort's first scan finds three pieces: [10, 20, 30] already ascending, [3, 2, 1] strictly descending, and [15, 25] ascending again. The descending piece gets reversed in place to [1, 2, 3], one cheap pass. Now the list is just three sorted runs, and the only work left is merging them. Merging three ready-made pieces costs far less than sorting eight items from nothing. Random data gives mostly tiny runs, so the run count climbs toward n itself, while nearly-sorted data gives a few long ones. The run count is a measurement of disorder, and Timsort's bill scales with it.

The consequence is dramatic, and I timed it on this machine with a million floats. Each figure is the best of 5 runs, so treat the milliseconds as indicative rather than exact:

n = 1_000_000                       # sorted() on different input orders
# random order    :  146.1 ms       <- the full n log n price
# already sorted  :    9.6 ms       <- ~15x faster: one giant run, near-linear
# reverse sorted  :   10.9 ms       <- ~13x faster: spots the descending run, flips it
# 20 sorted runs  :   10.6 ms       <- ~14x faster: merges 20 pre-made runs

On already-sorted data Timsort makes essentially one pass, confirms the whole list is one long run, and stops at O(n), not O(n log n). Reverse-sorted data is nearly as fast, because it spots a strictly descending run and flips it in place. That is why re-sorting a list you just nudged is almost free. The general bound is O(n log r), where r counts the runs already in the input. When the data is one big run (r = 1) the log term vanishes and you pay only O(n). When it is fully scrambled (r ≈ n) you pay the full n log n. So Timsort never beats the comparison floor on random data — the last section forbids that — but it pockets every scrap of order the input already has.

Step back and look at the arc of the chapter, because it lands somewhere real. We proved a floor that no comparison sort will ever break, not with any hardware, not in any century. Then we slid under it with counting sort by changing what a question is. We stacked that trick into radix sort, met the stability promise that holds it together, and found the same promise powering two-key sorts in everyday code. And Timsort folds the whole story into the one call you'll actually type, sorted(). So the next time it returns in a blink, you'll know it isn't magic. It is a theorem being respected and every loophole in it being cashed in, on your behalf, in C, under one Python name.

you type
$ python toolkit.py

from operator import itemgetter

words = ["kilo", "a", "delta", "bee"]
print(sorted(words, key=len))
print(sorted(words, key=len, reverse=True))
print(words)                                   # untouched -- sorted() copies

xs = [3, 1, 2]
print(xs.sort(), xs)                           # .sort() returns None

tracks = [("Titanium", "Sia", 245),
          ("Chandelier", "Sia", 216),
          ("Blinding Lights", "The Weeknd", 200),
          ("Elastic Heart", "Sia", 250),
          ("Save Your Tears", "The Weeknd", 215),
          ("Levitating", "Dua Lipa", 203)]

print(sorted(tracks, key=itemgetter(1))[0])
print(sorted(tracks, key=lambda t: (t[1], -t[2]))[:2])

# ---------- stability, proven: sort twice, the LAST key wins primary ----------
two_pass = sorted(tracks, key=itemgetter(2), reverse=True)   # secondary first
two_pass = sorted(two_pass, key=itemgetter(1))               # primary last
one_pass = sorted(tracks, key=lambda t: (t[1], -t[2]))
print(two_pass == one_pass)
for name, artist, secs in two_pass:
    print(f"  {artist:<11} {secs:>4}  {name}")

# ---------- stability, in miniature ----------
pairs = [("b", 1), ("a", 1), ("c", 0), ("d", 1), ("e", 0)]
print(sorted(pairs, key=itemgetter(1)))

print(min(tracks, key=itemgetter(2)), max(tracks, key=itemgetter(2)))

you see
['a', 'bee', 'kilo', 'delta']
['delta', 'kilo', 'bee', 'a']
['kilo', 'a', 'delta', 'bee']
None [1, 2, 3]
('Levitating', 'Dua Lipa', 203)
[('Levitating', 'Dua Lipa', 203), ('Elastic Heart', 'Sia', 250)]
True
  Dua Lipa     203  Levitating
  Sia          250  Elastic Heart
  Sia          245  Titanium
  Sia          216  Chandelier
  The Weeknd   215  Save Your Tears
  The Weeknd   200  Blinding Lights
[('c', 0), ('e', 0), ('b', 1), ('a', 1), ('d', 1)]
('Blinding Lights', 'The Weeknd', 200) ('Elastic Heart', 'Sia', 250)

Sorting arranges data so you can find things fast — the next chapter is about the finding itself: searching & selection. How binary search pinpoints any item in a sorted array in O(log n) by halving the haystack instead of scanning it — and how the same halving idea plucks the median out of a billion numbers without ever sorting them. →