36Divide & conquer — the power of halving

In Chapter 35 we took the brute-force solution and learned to hunt for the wasted work buried inside it. Now we meet the sharpest waste-cutter there is, and it hides in one sentence: if you can split a problem cleanly in half, a version a thousand times bigger costs you only about ten more steps. Here's the plan: we'll pull the three-line template every divide-and-conquer algorithm shares out into the open. Then we'll derive why halving gives you log n depth, instead of just memorising the fact. After that we'll learn to read a recurrence the way you read a plain sentence. And we'll meet two genuine marvels. The first raises a number to the millionth power in just twenty-five multiplications. The second multiplies two 300,000-digit numbers faster than the schoolbook method any of us was ever taught. The whole way through, we keep asking the one question that decides everything. If I already had the answer for each half, could I stitch the whole answer together cheaply? By the end you'll reach for "can I split this?" the way a locksmith reaches for a pick. You'll reach for it on a bug in 2,000 lines, on a number between 1 and a million, on anything with a shape left to cut.

01Split, solve, stitch — the three-line template

Let's start with the shape, because every divide-and-conquer algorithm is the same three moves wearing different clothes. Divide: break the input into smaller pieces that keep the same shape as the original problem. Conquer: solve each piece by calling the very same procedure on it, because a piece is just a smaller version of the whole. That self-call is recursion from Volume 1, a function calling itself with each call getting a fresh frame on the stack. Combine: stitch the sub-answers back together into the answer for the whole input. Now watch where the difficulty actually lives, because it is almost never in the split. The hard thinking nearly always hides in the combine step. Get that stitch right, and the recursion machinery does everything else for free.

Merge sort is the cleanest example of the template alive. To sort a list, split it into two halves and sort each half by calling merge sort on it. Then merge the two sorted halves into one sorted list, repeatedly taking the smaller of the two front elements. The split is trivial, just a cut through the middle of the list. The genius lives in the merge, because two already-sorted lists fuse into one in a single walk down both. We step it line by line in trace T30, so here we care about the shape, not the mechanics.

Let's do one merge by hand, so the walk is in your fingers before any code. Take the two sorted halves [2, 5, 9] and [1, 7, 8], and keep a finger on the front of each. Compare the fronts: 2 versus 1, so 1 moves to the output and the right-hand finger advances. Now 2 versus 7 sends out 2, then 5 versus 7 sends out 5, then 9 versus 7 sends out 7, then 9 versus 8 sends out 8. The left list still holds 9, and with nothing left to compare against, it simply slides out last. The output reads [1, 2, 5, 7, 8, 9], fully sorted, after just 5 comparisons for 6 elements. Notice what made that possible: because each half was already sorted, the smallest unplaced value could only ever be at one of the two fronts. That is the whole reason one walk down both lists is enough.

def merge_sort(a):
    if len(a) <= 1:                 # a list of 0 or 1 is already sorted — the base case
        return a
    mid   = len(a) // 2             # DIVIDE: split point, right in the middle
    left  = merge_sort(a[:mid])     # CONQUER: sort the left half (same function, smaller input)
    right = merge_sort(a[mid:])     # CONQUER: sort the right half
    return merge(left, right)       # COMBINE: fuse two sorted halves into one

def merge(x, y):
    out, i, j = [], 0, 0
    while i < len(x) and j < len(y):   # walk both, always take the smaller front
        if x[i] <= y[j]: out.append(x[i]); i += 1
        else:            out.append(y[j]); j += 1
    return out + x[i:] + y[j:]         # one side is exhausted; append the rest

Read the top function as plain English: a one-element list is done — otherwise split, sort both sides, merge. The if len(a) <= 1 line is the base case, the floor where recursion stops instead of splitting forever. The left and right lines are the two recursive descents into the halves. The merge helper is the whole payoff. Because both inputs are already sorted, comparing only the two front elements is enough to know which value comes next globally. I ran this on random lists from 1 to 100,000 elements, and every output came back in perfect ascending order. The number of comparisons tracked n·log₂n closely too: 100,000 items took 1,536,134 comparisons, against a predicted n·log₂n ≈ 1,660,964.

The split gives you a tree. How tall is that tree — and why does its height decide everything? →

02Why halving buys you log n

Let's start with a search space of one billion items and keep throwing away half. A billion becomes 500 million, then 250 million, and the pile keeps collapsing like that. So how many throws do we need before exactly one item is left standing? Not a billion, and not a thousand either. Thirty. That number, the count of times you can halve n before you hit 1, is the definition of log₂ n, the base-2 logarithm. It is the exact inverse of doubling, and that framing is worth holding onto. Doubling asks "start at 1, how many doublings to reach n?", and halving asks the same question backwards. I checked the whole ladder in Python: n = 1,000,000 takes 20 halvings, and 1,000,000,000 takes 30. Even 8,000,000,000, one item for every human alive, takes just 33.

import math
for n in [1_000, 1_000_000, 1_000_000_000, 8_000_000_000]:
    print(n, "halvings to reach 1:", math.ceil(math.log2(n)))
# 1000 -> 10 · 1_000_000 -> 20 · 1_000_000_000 -> 30 · 8_000_000_000 -> 33

This is exactly why binary search, stepped in trace T23, finds any name in a sorted phone book of eight billion in just 33 comparisons. Each comparison discards half of the remaining names in one stroke. The same fact explains why merge sort's tree is only log₂ n levels deep. Every level halves the piece size, so after log₂ n halvings the pieces are single elements. A million-element merge sort is a tree just 20 levels tall. Depth is logarithmic because halving is the inverse of doubling — everything else in this chapter is a consequence of that one fact.

you type
# ---------- halving.py ----------
import time, tracemalloc

a = [5, 2, 8, 1, 9, 3, 7]
mid = len(a) // 2
print("len(a) =", len(a), " mid =", mid, " left =", a[:mid], " right =", a[mid:])
print("the halves always tile the whole:", a[:mid] + a[mid:] == a)
print("odd length, so the left half is the smaller one:", len(a[:mid]), "vs", len(a[mid:]))

def find_slice(a, x):                 # halve with SLICES -- a copy at every level
    if not a: return False
    m = len(a) // 2
    if a[m] == x: return True
    return find_slice(a[:m], x) if x < a[m] else find_slice(a[m + 1:], x)

def find_index(a, x, lo=0, hi=None):  # halve with INDICES -- nothing copied
    if hi is None: hi = len(a)
    if lo >= hi: return False
    m = (lo + hi) // 2
    if a[m] == x: return True
    return find_index(a, x, lo, m) if x < a[m] else find_index(a, x, m + 1, hi)

big = list(range(1_000_000))          # 20 halvings either way -- time and peak memory
print("\nsame 20 halvings, 1,000,000 sorted items, looking for the last one")
for fn in (find_slice, find_index):
    tracemalloc.start(); t0 = time.perf_counter()
    hit = fn(big, 999_999)
    dt = (time.perf_counter() - t0) * 1000
    peak = tracemalloc.get_traced_memory()[1] / 1024 / 1024; tracemalloc.stop()
    print(f"  {fn.__name__:<11} found={hit}  {dt:>8.3f} ms   peak extra memory {peak:>7.2f} MiB")

$ python halving.py

you see
len(a) = 7  mid = 3  left = [5, 2, 8]  right = [1, 9, 3, 7]
the halves always tile the whole: True
odd length, so the left half is the smaller one: 3 vs 4

same 20 halvings, 1,000,000 sorted items, looking for the last one
  find_slice  found=True     4.073 ms   peak extra memory    7.63 MiB
  find_index  found=True     0.037 ms   peak extra memory    0.00 MiB

And now the lede's strange promise pays off, so let's cash it with arithmetic you can check. Ten doublings starting from 1 give 2, 4, 8, 16, 32, 64, 128, 256, 512, then 1,024. So ten doublings multiply a number by 1,024, which is almost exactly a thousand. Run that backwards: making a problem a thousand times bigger adds only about ten more halvings before you are back down to 1. You can see it in the ladder we just measured, where a million took 20 halvings and a billion took 30. That thousandfold jump, from a million to a billion, cost exactly ten extra steps. This is the property that makes log₂ n feel like a cheat code. The input grows by multiplication, but the cost only grows by addition.

Turn the knob yourself and feel the claim from the lede become physical. Push n up by a factor of a thousand, and watch the recursion depth crawl up by only ten. The same jump would make a linear algorithm choke, yet here it barely makes the tree taller.

So the tree is log n tall. But each level does some work too. How do the two multiply into a total? →

03Reading the recurrence: T(n) = a·T(n/b) + f(n)

The running time of any divide-and-conquer algorithm is captured by one line, called the recurrence. Read it as a sentence rather than a formula, and it stops being scary. T(n) simply means "the time to solve a problem of size n." The letter a counts the pieces you recurse into, and T(n/b) is the time for one piece, which is 1/b the size of the original. Then f(n) is the work you do yourself at this level, splitting the input and combining the answers. For merge sort you make a = 2 recursive calls, each on a half, so b = 2. The merge scans all n elements, so f(n) = n, and the whole sentence reads T(n) = 2·T(n/2) + n.

Before we solve the recurrence in general, let's feel it on a number small enough to trust. Give a one-element list a cost of T(1) = 1 and unroll upward from there. A two-element sort costs T(2) = 2·T(1) + 2 = 4, two tiny solves plus a two-element merge. Four elements cost T(4) = 2·T(2) + 4 = 12, and eight cost T(8) = 2·T(4) + 8 = 32. Now check that against where we are heading: n·log₂ n for n = 8 is 8 × 3 = 24 units of merge work, plus the 8 units the leaves cost, giving exactly 32. The recurrence and the tree agree on a number you can verify with a pencil. Hold onto that unrolling instinct, because the next paragraph does the same thing for every n at once.

You can solve this recurrence by pure counting, and you will not need a single theorem. Draw the tree and start adding up the work level by level. The top level does n units of merge work all by itself. It has two children, each doing n/2, which together comes to n again. Their four grandchildren each do n/4, and together those four also total n. Every level sums to n, because the pieces shrink by exactly the factor that they multiply in number. And from the last section we already know how many levels there are: log₂ n. So the total is n per level times log₂ n levels, which is n·log₂ n. You just derived merge sort's complexity by adding up a tree, nothing memorised anywhere.

The Master Theorem is just this counting argument, generalised, boiled down to a three-way comparison you can do in your head. It pits the work you do at the top (f(n)) against the work piling up in the leaves (which grows like n^(log_b a)). Whichever side is bigger wins the total:

• Leaves win (many small pieces, cheap combine): the answer is dominated by the bottom of the tree — total ≈ n^(log_b a).
• It's a tie (both sides balanced — merge sort's case): every level contributes equally, so you pay the per-level work times the log n levels — total ≈ f(n)·log n.
• The top wins (expensive combine, few pieces): the very first level dominates and the recursion is a rounding error — total ≈ f(n).

That is the whole theorem in plain words: compare the splitting/combining work to the work waiting in the subproblems — the bigger one sets the price. You will almost never need the formal version in day-to-day work. But here it is, written out properly, for the day you do.

Watch the tie happen with your own hands, because the slider below makes it visible. Slide n and see every level of the tree carry the same total load. The number of levels sets the total, and the total follows n log₂ n exactly. Meanwhile the quadratic method it beats balloons clean out of the frame within a few clicks.

04Fast exponentiation — xn in log n multiplications

Here is the marvel. To compute xn the obvious way, you multiply x by itself n−1 times, so 2¹⁰⁰⁰⁰⁰⁰ would cost 999,999 multiplications. But multiplication has a hidden gear: you can double the exponent with a single squaring. Square x² and you get x⁴, square again for x⁸, then x¹⁶, and so on up the ladder. Each squaring doubles the exponent instead of adding one to it. And doubling, we now know cold, reaches any target in log₂ n steps. So build the exponent up in powers of two, and multiply in the pieces the binary form of n tells you to keep.

That is exponentiation by squaring. Write n in binary; walk its bits from the top; square the running result at every bit, and multiply in an extra x whenever the bit is 1. The multiplication count is (bit_length − 1) squarings plus (popcount − 1) extra multiplies, where popcount is the number of 1-bits. I ran the counter:

def fast_pow(x, n):
    result = 1
    for bit in bin(n)[2:]:      # binary digits of n, most-significant first
        result = result * result        # SQUARE — doubles the exponent so far
        if bit == '1':
            result = result * x          # MULTIPLY — add one to the exponent
    return result

# verified against Python's own x**n on 2000 random cases: all equal.
# 2 ** 1_000_000:  bin(n) has 20 bits, 7 of them are 1
#   -> 20 squarings + 7 multiplies = 27 executed (the leading 1*1 square and 1*x multiply are trivial, so 19+6 = 25 do the real work)
#   the naive loop would need 999,999.

Line by line: result starts at 1, holding an accumulated exponent of zero. For each binary digit of n from the most significant down, we square result, which doubles the exponent we have accumulated so far. Then, if the current bit is a 1, we do one extra multiply by x, nudging the exponent up by one to match that bit. Now run the numbers. Because 1000000 is binary 11110100001001000000, which has 20 bits and 7 ones, the machine needs 19 squarings + 6 multiplies = 25 multiplications to produce a number with 301,030 decimal digits. Twenty-five, not a million. I verified fast_pow against Python's built-in x**n on 2,000 random inputs, and every result matched. Better still, Python's own integer ** uses exactly this trick internally.

Run the loop by hand on a small exponent and the trick stops feeling like magic. Take x¹³, and note that 13 in binary is 1101, which is 4 bits with 3 ones. The leading 1 just loads x into result, so the exponent we hold is 1. The next bit is a 1: square to get x², then multiply to get x³. The next bit is a 0: square to get x⁶ and do nothing else. The last bit is a 1: square to get x¹², then multiply to reach x¹³. Read the exponents we passed through: 1, 3, 6, 13 — those are exactly the prefixes of 1101, because squaring shifts the binary exponent left and the extra multiply sets its lowest bit. Total cost: 3 squarings + 2 multiplies = 5 multiplications, against the naive method's 12. And the formula from above agrees, since bit_length 4 minus 1 gives the 3 squarings and popcount 3 minus 1 gives the 2 extras.

Turn the exponent yourself in the explorable below. Watch the binary of n decide which steps are plain squares and which ones add a multiply. And watch the fast count sit near log₂ n while the naive count runs off to n without ever looking back.

Squaring made powers cheap by halving the exponent. Could the same halving instinct make plain old multiplication of giant numbers cheaper than the method you learned in school? →

05Karatsuba — multiplying giants below n²

The multiplication you learned as a child is O(n²). To multiply two n-digit numbers, every digit of one meets every digit of the other, making n × n little products. Double the digit count and the work quadruples. For the 300,000-digit numbers that 2¹⁰⁰⁰⁰⁰⁰ produces, that quadratic cost is brutal. For a long time, people widely assumed that n² was simply the price of multiplication. Then in 1960, following a question the mathematician Andrey Kolmogorov had posed, a young student named Anatoly Karatsuba found a method that beat it. The surprise reshaped how people thought about the limits of arithmetic.

The trick is divide and conquer with one stroke of genius on top. Split each n-digit number into a high half and a low half: x = a·10^(n/2) + b and y = c·10^(n/2) + d. The schoolbook product needs the four cross-products ac, ad, bc, and bd. That is 4·T(n/2), and four turns out to be too many, because four gives you back n². Karatsuba noticed that the middle term ad + bc can be recovered from products you already need plus one more. Here is why: (a+b)(c+d) = ac + ad + bc + bd, so ad + bc = (a+b)(c+d) − ac − bd. That means three multiplications suffice instead of four: ac, bd, and (a+b)(c+d). One saved multiplication, taken recursively at every level, changes the exponent itself.

Watch it work once on numbers small enough to check in your head. Multiply 47 by 62, so a = 4, b = 7, c = 6, d = 2. The three products are ac = 24, bd = 14, and (a+b)(c+d) = 11 × 8 = 88. Recover the middle term by subtraction: 88 − 24 − 14 = 50. Now assemble the answer: 24·100 + 50·10 + 14 comes to 2400 + 500 + 14 = 2914. Check it the long way and 47 × 62 is indeed 2,914. We spent three real multiplications where schoolbook spends four, and we paid for the saving with a few additions and subtractions. Those extras are cheap, costing only linear time in the digit count. That trade, expensive multiplies swapped for cheap adds, is the entire economic logic of Karatsuba.

Why does dropping 4 to 3 change the exponent? Straight from the recurrence. Schoolbook is T(n) = 4·T(n/2) + n; Karatsuba is T(n) = 3·T(n/2) + n. By the watershed rule, the leaf work grows as n^(log₂ a): log₂4 = 2 gives n²; log₂3 ≈ 1.585 gives n^1.585. A single fewer branch per node, compounded over log n levels, bends the whole curve. This is not folklore — Python's own big integers use it. CPython multiplies small integers the schoolbook way but switches to Karatsuba once the numbers pass a threshold. I timed multiplication of random numbers as their size doubled:

import random, time
def t(bits, reps):
    a, b = random.getrandbits(bits), random.getrandbits(bits)
    a * b                                   # warm up
    s = time.perf_counter()
    for _ in range(reps): a * b
    return (time.perf_counter() - s) / reps

#  bits     time/mult     ratio when bits double   (schoolbook would be 4.0x)
#  64000    8.2e-4 s
# 128000    2.4e-3 s      2.92x      implied exponent log2(2.92) ~ 1.55
# 256000    7.5e-3 s      3.05x      implied exponent log2(3.05) ~ 1.61

Read the ratios in that table slowly, because they are the whole story. Every time the numbers doubled in length, the time grew by about 3×, not the 4× that schoolbook n² demands. Take log₂ of that measured ratio and you get roughly 1.58, landing right on Karatsuba's theoretical log₂3 = 1.585. These are wall-clock timings on this machine, so the exact milliseconds will differ on yours. But the ratio, the slope, is a property of the algorithm and not the hardware. You are watching a 1960 theorem tick inside your interpreter every time you multiply large integers.

Splitting bought us logarithmic depth, cheap powers, sub-quadratic products. But there's one more prize hiding in the word independent — and it's about the metal. →

06The metal, and the mental move

Look back at the merge-sort tree one more time. The left half and the right half never touch until the merge. They are independent, meaning nothing the left recursion computes changes anything the right one does. That independence is a gift to the hardware, and Volume 1 told you why: a modern CPU has many cores. Independent subproblems can be handed to different cores at the same time. Sort the left half on core 0 while core 1 sorts the right, then merge. Divide and conquer is the most natural way there is to write parallel code, because the algorithm has already carved the work into pieces that don't interfere. And this is not a metaphor — it is the exact shape of MapReduce, the pattern that let Google process the whole web across thousands of machines. Split the data, solve the shards in parallel, combine — divide and conquer at datacenter scale.

One honest caveat before you file that away as a free lunch. The recursive solves parallelise beautifully, but the final top-level merge still walks all n elements, and in the simple scheme it walks them on a single core. So doubling the core count does not simply halve the wall-clock time, because the serial combine step stays in the bill. Engineers work around it, with parallel merge algorithms and with trees that fan out wider than two. But the shape of the limit is worth naming now: a parallel speedup is capped by whatever fraction of the work refuses to be split. You will meet that idea again wherever parallel hardware appears, and divide and conquer is the cleanest place to first see it.

There is a cache dividend too, straight from Volume 1's memory hierarchy. When a subproblem shrinks enough to fit entirely in fast cache, every remaining operation on it runs at cache speed. It stops paying for round trips out to main memory. Recursion naturally drives the working set down to that sweet spot, because every split shrinks the data in play. That is why cache-aware divide-and-conquer sorts and matrix multiplications routinely beat "flat" algorithms with the identical Big-O. Same curve on paper, but the one whose data sits in cache wins the wall clock. This is the recurring lesson of the whole volume: at equal Big-O, constants and data layout decide the race.

Now for the mental move, the thing to carry out of this chapter into problems that have nothing to do with sorting. When you face an unknown, ask what single question cuts the space of possibilities in half. Say a bug appears somewhere in 2,000 lines of new code, and don't read line 1 and creep forward. Comment out half, see which half misbehaves, and repeat on the guilty half until the bug stands alone. Eleven steps, not two thousand. This is literally what git bisect does: it binary-searches your commit history for the one commit that broke the build, in log₂ of your commits. Or say a number hides somewhere between 1 and a million and you get hot/cold hints. Guess the middle every time and the hints corner it in twenty guesses. A wide spreadsheet has one wrong total? Split it, sum each half, and chase whichever half's sum comes out wrong. Halving is not a sorting technique at all. It is a way of attacking uncertainty, and once you see it, you will see it everywhere.

"""merge_yourself.py -- write merge, and merge_sort falls out of it."""
import random
from math import log2

CMP = 0                                    # one global counter, so we can audit the cost

def merge(x, y):
    """Fuse two ALREADY-SORTED lists into one sorted list, in a single walk."""
    global CMP
    out, i, j = [], 0, 0
    while i < len(x) and j < len(y):       # while BOTH still have a front element
        CMP += 1
        if x[i] <= y[j]:                   # <= not < : ties take the LEFT one (stability)
            out.append(x[i]); i += 1
        else:
            out.append(y[j]); j += 1
    return out + x[i:] + y[j:]             # exactly one side is non-empty; append it whole

def merge_sort(a):
    if len(a) <= 1:                        # the base case: 0 or 1 items is already sorted
        return a
    mid = len(a) // 2
    return merge(merge_sort(a[:mid]), merge_sort(a[mid:]))

print("merge([2, 5, 9], [1, 7, 8]) ->", merge([2, 5, 9], [1, 7, 8]), f"in {CMP} comparisons")

random.seed(36)                            # seeded: this run is reproducible on your machine
for n in (0, 1, 2, 17, 1_000):             # the sizes that break naive merge sorts
    a = [random.randrange(1_000) for _ in range(n)]
    out = merge_sort(a)
    assert out == sorted(a), n             # sorted AND the same multiset -- both, every time
print("edge sizes 0, 1, 2, 17, 1000: every output equals sorted(a)")

ok = 0
for _ in range(500):                       # 500 random lists, adversarially duplicate-heavy
    a = [random.randrange(20) for _ in range(random.randint(0, 60))]
    assert merge_sort(a) == sorted(a)
    ok += 1
print(f"{ok} random lists (heavy duplicates), 0 mismatches")

CMP = 0
n = 100_000
big = [random.randrange(10 ** 9) for _ in range(n)]
assert merge_sort(big) == sorted(big)
print(f"n = {n:,}: {CMP:,} comparisons   vs the n*log2(n) ceiling of {n * log2(n):,.0f}")

class Track:                               # compares on plays ONLY, so ties stay visible
    def __init__(s, name, plays): s.name, s.plays = name, plays
    def __le__(s, o): return s.plays <= o.plays
    def __lt__(s, o): return s.plays <  o.plays
    def __repr__(s): return f"{s.name}({s.plays})"

tracks = [Track("Levels", 2), Track("Faded", 1), Track("Titanium", 2)]
print("stable, because of the <= :", merge_sort(tracks))

def merge_strict(x, y):                    # the SAME walk with < instead of <=
    out, i, j = [], 0, 0
    while i < len(x) and j < len(y):
        if x[i] < y[j]: out.append(x[i]); i += 1
        else:           out.append(y[j]); j += 1
    return out + x[i:] + y[j:]

def merge_sort_strict(a):
    if len(a) <= 1: return a
    m = len(a) // 2
    return merge_strict(merge_sort_strict(a[:m]), merge_sort_strict(a[m:]))

print("one character later  (<) :", merge_sort_strict(tracks), " <- the tie flipped")


# ---------- what it printed ----------
#
# merge([2, 5, 9], [1, 7, 8]) -> [1, 2, 5, 7, 8, 9] in 5 comparisons
# edge sizes 0, 1, 2, 17, 1000: every output equals sorted(a)
# 500 random lists (heavy duplicates), 0 mismatches
# n = 100,000: 1,536,317 comparisons   vs the n*log2(n) ceiling of 1,660,964
# stable, because of the <= : [Faded(1), Levels(2), Titanium(2)]
# one character later  (<) : [Faded(1), Titanium(2), Levels(2)]  <- the tie flipped
#
#
# ---------- the three things that run is telling you ----------
#
# THE COMPARISON COUNT.  1,536,317 real comparisons against a predicted
# n*log2(n) = 1,660,964. Under the ceiling, and within 8% of it -- because the
# last element of one half often lands without any comparison at all. You
# derived that ceiling by adding up the tree; this is the tree, audited.
#
# THE ONE LINE THAT DOES THE WORK.  `return out + x[i:] + y[j:]` is where the
# leftover tail goes. Exactly one of those two slices is non-empty, and it is
# already sorted, so no comparison is needed to place it. Beginners write a
# second while-loop here; the slice says it in one line.
#
# WHAT `<` BROKE.  Nothing that any assertion could catch -- the output is
# still perfectly sorted. What you lost is STABILITY: with `<=`, a tie hands
# the slot to the LEFT element, so equal items keep the order they arrived in.
# With `<`, the right one jumps ahead, and Levels/Titanium swap. That matters
# the moment you sort by one field and expect the previous sort to survive --
# sort by plays, then by name, and only a stable sort keeps both. Python's own
# sorted() is stable, and this single character is why.

Next chapter turns from splitting to a different instinct entirely: hashing — how spending a little memory lets a dict answer "is this thing in here?" in a single O(1) jump instead of an O(n) scan, deleting whole inner loops on sight and collapsing O(n²) to O(n). What can you buy by trading space for time? →