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

3. Making the staircase visible

Every call in §2 ran at some depth — Hanoi-for-3 paused while Hanoi-for-2 worked, which paused for Hanoi-for-1. The machine keeps the paused calls on its stack; let’s print the stack’s shape directly. Pass the depth along, and indent by it:

def hanoi_trace(n, source, target, spare, depth):
    print("  " * depth, "want", n, "disks:", source, "->", target)
    if n == 1:
        print("  " * depth, "move disk 1")
        return
    hanoi_trace(n - 1, source, spare, target, depth + 1)
    print("  " * depth, "move disk", n)
    hanoi_trace(n - 1, spare, target, source, depth + 1)

hanoi_trace(3, "A", "C", "B", 0)

(" " * depth is a small Python kindness: a string times a number repeats it.) Run it and read the left margin: the indentation breathes in and out, deeper as work is delegated, shallower as delegations finish. That margin is the call stack — the deep-water box made of whitespace. Draw the same shape by hand for hanoi_trace(2, ...) before believing the machine’s.

4. Merge sort, audited

The chapter sorted cards: split, sort each half somehow, merge. The merge first — it is where all real work happens:

def merge(left, right):
    result = []
    i = 0                      # finger on left pile
    j = 0                      # finger on right pile
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i = i + 1
        else:
            result.append(right[j])
            j = j + 1
    while i < len(left):       # one pile ran dry; sweep the other in
        result.append(left[i])
        i = i + 1
    while j < len(right):
        result.append(right[j])
        j = j + 1
    return result

print(merge([2, 9, 11, 30], [4, 5, 12, 28]))

Two fingers, two piles, always take the smaller top card — the code is your hands from the chapter. Now the recursion around it, with one new piece of notation: items[:mid] is the list up to position mid, and items[mid:] is the rest. Splitting is the idea; the colon is just its spelling.

def merge_sort(items):
    if len(items) <= 1:        # the floor: tiny piles are born sorted
        return items
    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])
    return merge(left, right)

print(merge_sort([7, 3, 9, 1, 8, 2, 6, 4]))

Eight lines around a merge. Test it on your own lists — include an empty list, a one-item list, a list with repeats, a list already sorted backward. (Testing the edges first is a habit worth stealing from professionals; Chapter 1’s human moment is the reason the habit exists.)

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