A First Taste of Algorithms · Lab 3: The Visible Staircase

5. The bill, audited

The chapter promised C(n) ≈ n log₂ n in the currency of element-steps — one step per card the merge touches. Send the count climbing back up the recursion alongside the sorted list; the function now returns a two-item list, [sorted, steps]:

def merge_sort_count(items):
    if len(items) <= 1:
        return [items, 0]
    mid = len(items) // 2
    left = merge_sort_count(items[:mid])
    right = merge_sort_count(items[mid:])
    merged = merge(left[0], right[0])
    steps = left[1] + right[1] + len(merged)   # this merge touches every card once
    return [merged, steps]

Now the audit, in the style of Lab 1’s race — and watch the per-item column:

for n in [1000, 10000, 100000, 1000000]:
    items = list(range(n, 0, -1))          # n, n-1, ..., 1: sorted backward
    result = merge_sort_count(items)
    steps = result[1]
    print(n, steps, "steps;", steps / n, "per item")

The left column multiplies by 10; the per-item column climbs by a little over 3 each row. You have seen that gait before — it is the logarithm’s, from Chapter 1’s table, now appearing as the per-item price of sorting. Total steps ≈ n × (log₂ n-ish per item): the tree’s level-count, measured in the wild. Check one row against arithmetic: for n = 1,000,000, is steps close to 20 million?

Break it

Predict first. Run second. Explain any gap third.

1. Starve countdown of its floor: delete the if n == 0: block (keep the rest) and call countdown(5). Predict precisely what the machine will do — forever? crash? something else? — then run it and read the error to its last line. The number it complains about (Python’s recursion limit, near a thousand) is the deep-water box’s claim that the stack is physical, demonstrated. How is this failure different in kind from Sevenia’s in Lab 2 — which lab’s program was wrong, and which was exhausted?

2. In hanoi, swap the two recursive calls (clear-the-way and restack trade places). Predict: will the printed moves still be legal — no large disk onto a small one? Then run it for n = 3 and audit the move list with your coins, move by move. Find the first illegal moment and describe which trust was betrayed.

3. In merge_sort_count, change mid = len(items) // 2 to mid = 1: every split now peels a single card off the front instead of halving. Two predictions before running: is the output still correct? and what happens to the cost — per-item column flat-ish like the logarithm, or growing with n? Audit the lopsided version on sizes 200, 400, 800 (not the big sizes — you’ll discover why in a moment) and look at the total steps as n doubles. Doubling the input does what to the bill? Connect it to the chapter’s closing sentence: where a recursion sends its work is the whole game. You have just met, in your own code, the difference between n log n and n² — Chapter 6 makes it official. Then, deliberately, run size 2,000 and read the error to its last line: the lopsided tree is n calls deep where the balanced tree was log₂ n deep, and the machine’s stack — Break-it 1’s discovery — just refused the architecture, not the arithmetic.

4. In merge, change <= to <. Predict whether any list of numbers can ever come out unsorted. Run your tests; they should all pass. So the character changed nothing? To find out, sort things that can genuinely tie. Make each item a [score, name] pair and — one more edit — make the merge compare scores only: change the comparison line to if left[i][0] <= right[j][0]:. Now sort [[3, "Ada"], [1, "Hua"], [3, "Noether"]] with the <= version and the < version and compare the outputs. What happened to the two score-3 students, and which version keeps tied items in their original order? (Chapter 6 names this property; you have discovered it early. And a side puzzle: why did the experiment need the scores-only edit — what was Python quietly doing with the pairs before it?)

All 32 chapters of A First Taste of Algorithms · Foundations · All courses