A First Taste of Algorithms · Lab 6: Counted and Clocked

3. The clock arrives — with a protocol

Python’s stopwatch is time.perf_counter(): call it, do work, call it again, subtract. But a computer is a busy place — your timing shares the machine with everything else running — so single measurements lie. The professional protocol: repeat many times, take the median (the middle value when sorted — outliers from a busy moment fall off the ends).

import time

def clock(sorter, items, repeats):
    times = []
    for _ in range(repeats):
        copy = list(items)
        start = time.perf_counter()
        sorter(copy)
        times.append(time.perf_counter() - start)
    times.sort()                      # the built-in sort; §6 turns the clock on it
    return times[len(times) // 2]     # the median

(Note the line copy = list(items): each repeat sorts a fresh copy. For an in-place sorter this is not tidiness, it is the experiment’s integrity — predict what the second repeat would be measuring without it, then hold the thought for Break-it 2.)

4. The clocked race, and the neighborhood

Now both sorts on the clock. Plain versions without counters (retype merge_sort from Lab 3; write insertion_sort by deleting the counter from §1), shuffled inputs this time — the clock’s question is “typical day,” and random.shuffle deals one:

import random
random.seed(7)                        # same shuffles every run: experiments should repeat

for n in [4, 8, 16, 32, 64, 128, 256]:
    items = list(range(n))
    random.shuffle(items)
    t_ins = clock(insertion_sort, items, 51)
    t_mrg = clock(merge_sort, items, 51)
    winner = "insertion" if t_ins < t_mrg else "merge"
    print(n, "  insertion:", round(t_ins * 1e6, 1), "µs   merge:",
          round(t_mrg * 1e6, 1), "µs   →", winner)

Predict before running: §2 said merge wins every count — does it win every clock? Then read the table. On most machines a neighborhood appears at small n where insertion wins the clock while losing the count: the plodder is a simple creature with almost no overhead, and at a dozen items, overhead is most of the bill. Find your machine’s crossover point (the n where the winner flips) and write it down — it is data for Problem 2.1, and it is the constant factor, located. The count predicted the shapes; the constants own the neighborhood.

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