Algorithms and Efficiency

There is almost always more than one algorithm for a job. To choose between them, programmers ask three questions:

• Is it correct? Does it give the right answer for every input, including the edges? (You tested algorithms this way in Grade 8.)
• Is it efficient? How much work does it do: how many steps, and how much memory? An algorithm that does less work for the same job is more efficient.
• Is it clear? Can another person (or you, next month) read it, check it and change it without making mistakes?

Here are two functions that add up the whole numbers from 1 to n. The first adds them one at a time, like Grade 8’s running totals. The second uses a formula from mathematics: the sum of 1 to n is n(n + 1) ÷ 2.

def total_loop(n):    total = 0    for k in range(1, n + 1):        total = total + k    return total def total_formula(n):    return n * (n + 1) // 2 for n in [1, 10, 100, 1000]:    print(n, total_loop(n), total_formula(n), total_loop(n) == total_formula(n))

1 1 1 True10 55 55 True100 5050 5050 True1000 500500 500500 True

Correct? Both pass every test: the same answer for 1 (an edge), 10, 100 and 1000. (Tests can never prove a function right, as Grade 8 said; but the formula is proved in mathematics, and the loop does exactly what “add them up” means.)

Efficient? For n = 1000, the loop does 1000 additions. The formula does one addition, one multiplication and one division, whatever n is. For a million, the loop does a million additions; the formula still does three steps.

Clear? The loop says exactly what it does. The formula is shorter, but a reader must know the mathematics to trust it, so it deserves a comment saying where it comes from.

So the formula wins on efficiency, and both are correct. Very often the choice is like this: a simple algorithm that is easy to check, and a cleverer one that does much less work.

Count steps, not seconds

Why count additions instead of timing the two functions with a clock? Because the time depends on things that have nothing to do with the algorithm: how fast the computer is, which language it runs, what else it is doing. A phone might take ten times as long as a laptop for the same program. But the loop makes 1000 additions on both. Counting steps, the actions an algorithm repeats, measures the algorithm itself.

Which actions count as a step? The one the algorithm repeats most, which takes most of the time: in a search or a sort, the comparisons; in a total, the additions. You don’t need to count every line, because in a long run the line that repeats most decides everything.

A program that counts its own steps needs only one more variable: a counter, set to 0, with 1 added at every step. Here are Grade 8’s two searches, each counting its looks and returning the count beside its answer, as a tuple (Unit 3). The program then searches bigger and bigger lists, doubling the length each time, for a number that isn’t there: the worst case for both.

def linear_search(items, target):    looks = 0    for i in range(len(items)):        looks = looks + 1        if items[i] == target:            return i, looks    return -1, looks def binary_search(items, target):    low = 0    high = len(items) - 1    looks = 0    while low <= high:        middle = (low + high) // 2        looks = looks + 1        if items[middle] == target:            return middle, looks        elif items[middle] < target:            low = middle + 1        else:            high = middle - 1    return -1, looks n = 1000while n <= 16000:    numbers = list(range(n))    where, linear = linear_search(numbers, n)    where, binary = binary_search(numbers, n)    print(f"{n:>6} items: linear {linear:>6} looks, binary {binary:>3} looks")    n = n * 2

  1000 items: linear   1000 looks, binary  10 looks  2000 items: linear   2000 looks, binary  11 looks  4000 items: linear   4000 looks, binary  12 looks  8000 items: linear   8000 looks, binary  13 looks 16000 items: linear  16000 looks, binary  14 looks

list(range(n)) makes a sorted list of the numbers 0 to n − 1, so the target n is never there. {n:>6} in the f-string prints the number right-aligned in 6 places, so the columns line up.

Look at what happens each time the list doubles:

• Linear search’s looks double too: 1000, 2000, 4000. Twice the data, twice the work.
• Binary search needs just one more look: 10, 11, 12. Each look halves the list, so a list twice as long needs only one more halving.

This is the most useful question to ask about any algorithm: when the data doubles, what happens to the work? It tells you what the algorithm will do with data far bigger than you can test.

Doubling the data does very different things to different algorithms. There are six kinds of growth you will meet again and again, each with its own name. Here each one is a real algorithm, counted at its worst:

At ten million steps a second (about what Python manages on a fast computer; a phone is slower), the million-item column takes 0.0000001 seconds for constant, 0.1 seconds for linear, about 2 seconds for n log n, and about 14 hours for quadratic. The exponential one, even at 100 items, would take about 4 × 10¹⁵ years, hundreds of thousands of times the age of the universe.

Linear: one look at each

An algorithm that does a fixed amount of work for each item, once, is linear: twice the items, twice the steps. Linear search, adding up a bill, finding the highest mark and counting the words in a text are all linear. A linear algorithm is usually good enough: it reads each item only once, and many jobs can’t be done without reading every item at least once.

Logarithmic and constant: hardly any more work

An algorithm that throws away half of what is left at each step is logarithmic: twice the items, just one step more. The number of halvings is called the logarithm (to base 2) of n, written log₂ n: log₂ 1,024 = 10, because 2¹⁰ = 1,024. Binary search is the famous one.

An algorithm whose work doesn’t grow at all is constant. Reading marks[500] goes straight to position 500, however long the list. Looking up a key in a dictionary, as Unit 3 explained, works out where the value is kept from the key itself (hashing), so it usually takes one or two looks for a dictionary of ten items or ten million. Later in this unit you will time it.

Quadratic: every pair

Forty students meet, and each one shakes hands with every other one, once. How many handshakes? The first student shakes 39 hands. The second has already shaken the first’s hand, so 38 more; the third 37 more; and so on down to 0 for the last: 39 + 38 + … + 1 = 780.

In general, n things make n(n − 1) ÷ 2 pairs. For 40 students, 40 × 39 ÷ 2 = 780. Double the class to 80 and there are 80 × 79 ÷ 2 = 3,160 handshakes: about 4 times as many. That is quadratic growth, named after the square, n²: twice the items, four times the work; ten times the items, a hundred times the work.

Any program with a loop inside a loop, each going through the whole list, is usually quadratic. Program A at the start of this unit is one: it compares every identity number with every other.

def has_twin_pairs(numbers):    """Compare every pair: True if any two numbers are the same."""    comparisons = 0    for i in range(len(numbers)):        for j in range(i + 1, len(numbers)):            comparisons = comparisons + 1            if numbers[i] == numbers[j]:                return True, comparisons    return False, comparisons for n in [10, 20, 40, 80]:    numbers = list(range(n))    print(n, has_twin_pairs(numbers))

10 (False, 45)20 (False, 190)40 (False, 780)80 (False, 3160)

The inner loop starts at i + 1, so each pair is compared once, never a number with itself. The numbers 0 to n − 1 are all different, so every pair is compared: the worst case. Each doubling of n makes about 4 times as many comparisons.

Bubble sort is quadratic too. On a list that is backwards, its passes compare about n pairs, and it needs about n passes: about n × n comparisons. For 1,000 items that is about a million; for a million items, about a million million.

Exponential: every group

Before a trek to Annapurna Base Camp, Dawa has 20 things she might pack, and her bag must weigh 8 kg at most. Which things should she take to be most useful? The surest way is to try every group of things: for each thing, take it or leave it.

With 1 thing there are 2 groups (take it, or don’t). With 2 things, 4 groups; with 3 things, 8. Each new thing doubles the number of groups, because every old group can be tried with it and without it. So n things make 2ⁿ groups: for 20 things, 1,048,576. Add 10 more things and it is over a billion; at 60 things, over a billion billion.

Work that doubles each time one item is added is exponential. It isn’t just slow: it is hopeless for big n on any computer, now or ever. An exponential algorithm is used only when the data is small, or when nobody knows anything better. You met one in Unit 6: trying every key, where each bit added to a key doubles the attacker’s work. There, the slowness is the protection.

Naming the growth

Computer scientists write the kinds of growth with a capital O, for “order of”: an algorithm is O(n) (“order n”) if its work grows like n, O(n²) if like n². This way of writing is called Big-O notation. It keeps only the part that matters when n is big and drops the rest: n(n − 1) ÷ 2 handshakes is O(n²), because for a big n the − 1 and the ÷ 2 hardly change how fast it grows.

You won’t need to prove these. What you need is the habit of asking how the work grows, and of recognizing the kinds when you see them.

Once you can count the work, you can improve an algorithm and measure the improvement. There are two common ways: a better loop, which stops doing work that isn’t needed, and a better plan, often put into a function of its own, which does the job a different way.

A better loop: shorter passes

Look again at Grade 8’s bubble sort. After the first pass, the biggest item has been carried all the way to the right end: it is settled, in its final place. After the second pass, the second biggest is settled next to it. Yet every pass compares all the way to the end, comparing settled items again and again, although nothing there can ever change.

The better loop: each pass stops one place earlier than the one before. Pass 1 compares n − 1 pairs, pass 2 compares n − 2, and so on.

def bubble_sort(items):    """Sort the list in place; return the number of comparisons."""    comparisons = 0    settled = 0    swapped = True    while swapped:        swapped = False        for i in range(len(items) - 1 - settled):            comparisons = comparisons + 1            if items[i] > items[i + 1]:                items[i], items[i + 1] = items[i + 1], items[i]                swapped = True        settled = settled + 1    return comparisons marks = [91, 85, 70, 62, 54, 47, 38, 29]print(bubble_sort(marks), marks)

28 [29, 38, 47, 54, 62, 70, 85, 91]

Two changes from Grade 8: the inner loop stops settled places before the end, and the swap uses Unit 3’s tuple unpacking, a, b = b, a, in place of a third variable. The answer is the same; only the work is less.

Half the work is a good improvement. But look at the counts as the list grows: shorter passes need n(n − 1) ÷ 2 comparisons at worst, which is still quadratic. For a million items, it is half of a million million. A better loop made bubble sort twice as fast; to go thousands of times faster, you need a better plan.

A better plan: three ways to find a repeat

Back to the identity numbers at the start of this unit. Here are the three programs, each as a function that counts its steps, so you can compare them on the same lists. Each returns True if any number appears twice.

def repeat_pairs(numbers):    """A: compare every pair."""    steps = 0    for i in range(len(numbers)):        for j in range(i + 1, len(numbers)):            steps = steps + 1            if numbers[i] == numbers[j]:                return True, steps    return False, steps def repeat_sorted(numbers):    """B: sort a copy, then compare neighbors (the sorting is not counted)."""    ordered = sorted(numbers)    steps = 0    for i in range(len(ordered) - 1):        steps = steps + 1        if ordered[i] == ordered[i + 1]:            return True, steps    return False, steps def repeat_dictionary(numbers):    """C: keep each number seen in a dictionary."""    seen = {}    steps = 0    for x in numbers:        steps = steps + 1        if x in seen:            return True, steps        seen[x] = True    return False, steps tests = [[5, 3, 9, 3], [5, 3, 9, 1], [7], [], list(range(1000))]for t in tests:    print(repeat_pairs(t)[0], repeat_sorted(t)[0], repeat_dictionary(t)[0])print(repeat_pairs(list(range(1000)))[1], repeat_sorted(list(range(1000)))[1], repeat_dictionary(list(range(1000)))[1])

True True TrueFalse False FalseFalse False FalseFalse False FalseFalse False False499500 999 1000

First, correctness: all three agree on every test, an ordinary list with a repeat, one without, and the edges of one item and no items, so the cleverer ones haven’t broken anything. Then efficiency, on 1,000 different numbers: A makes 499,500 comparisons; B makes 999 after sorting; C makes 1,000 dictionary looks.

• A is quadratic, O(n²).
• B’s neighbor check is linear, but sorting comes first. Python’s sorted() is an O(n log n) sort, the kind you will meet next, so B as a whole is O(n log n). Two equal numbers must end up side by side in a sorted list, which is why checking neighbors is enough.
• C is linear, O(n): one dictionary look for each number, and each look is constant time. It uses more memory than the others, though: the dictionary holds a copy of every number seen.

And clarity: each plan is a function with a docstring saying what it does, so a reader of the main program needs only the name. A is the easiest to understand; C is just as short and far faster. That is why C, or something like it, is what a real program would use.

Two teachers have each sorted their own class’s exam copies by roll number, and now the office wants one pile for the whole grade, in order. Nobody needs to sort it all again. Put the two piles side by side, face up, and look only at the two top copies. Take whichever has the smaller roll number and put it face down on a new pile. Look at the two tops again, and again take the smaller. When one pile is empty, put the rest of the other on the end: it is in order already.

Putting two sorted piles together into one sorted pile like this is called merging. Each comparison moves one copy to the new pile, so merging piles with n copies in all takes at most n − 1 comparisons. It is linear.

The algorithm

As numbered steps, the way the SEE asks for an algorithm:

Step 1: StartStep 2: Read the two sorted piles, A and BStep 3: Set C to an empty pileStep 4: Is A empty or B empty?        Yes: go to Step 7        No: go to Step 5Step 5: Is the top of A ≤ the top of B?        Yes: move the top of A to the end of C        No: move the top of B to the end of CStep 6: Go to Step 4Step 7: Put what is left of A, then what is left of B, on the end of CStep 8: Display CStep 9: Stop

And in Python. Instead of really taking copies off the piles, the function keeps two positions, i in pile a and j in pile b: the tops are a[i] and b[j].

def merge(a, b):    """Merge two sorted lists into one sorted list."""    c = []    i = 0    j = 0    while i < len(a) and j < len(b):        if a[i] <= b[j]:            c.append(a[i])            i = i + 1        else:            c.append(b[j])            j = j + 1    c = c + a[i:] + b[j:]    return c print(merge([38, 62, 85], [29, 47, 91]))print(merge([10, 20], [5, 15, 25, 35]))print(merge([], [4, 8]))

[29, 38, 47, 62, 85, 91][5, 10, 15, 20, 25, 35][4, 8]

The loop goes round while both piles still have a top. After it, a[i:] is what is left of a (a slice, Unit 3) and b[j:] what is left of b; one of them is empty, so adding both on the end is safe. <= takes from a when the two tops are equal, which keeps equal items in the order they came.

Sorting by merging

Merging is quick, but it needs piles that are sorted already. Where do they come from? Here is the trick: a pile of one item is always sorted. So:

1. Start with every item as a pile of one. With 8 items, that is 8 sorted piles.
2. Merge the piles in pairs: 4 sorted piles of 2.
3. Merge those in pairs: 2 sorted piles of 4.
4. Merge again: 1 sorted pile of 8. Done.

This is merge sort. Each round of merging halves the number of piles.

How much work?

In each round, every item is merged once, so a round makes at most n comparisons. How many rounds? Each round halves the number of piles, from n down to 1: that is log₂ n rounds, 3 for 8 items, 10 for 1,024. So merge sort makes at most about n × log₂ n comparisons: it is O(n log n).

For a million items, merge sort makes about 26,000 times fewer comparisons. That is the difference between a few seconds and almost 14 hours. (The merge sort column is exact: the most comparisons merge sort can ever need, n × ⌈log₂ n⌉ − 2^⌈log₂ n⌉ + 1, where ⌈ ⌉ means rounded up to a whole number.)

Here is merge sort in Python, using the merge function above (with a counter added). A function that has been written and tested once can be used as a building block: merge sort is a loop of merges.

def merge(a, b):    """Merge two sorted lists; return the new list and the comparisons."""    c = []    i = 0    j = 0    comparisons = 0    while i < len(a) and j < len(b):        comparisons = comparisons + 1        if a[i] <= b[j]:            c.append(a[i])            i = i + 1        else:            c.append(b[j])            j = j + 1    c = c + a[i:] + b[j:]    return c, comparisons def merge_sort(items):    """Return a sorted copy of the list, and the comparisons made."""    piles = []    for x in items:        piles.append([x])    comparisons = 0    while len(piles) > 1:        merged = []        for k in range(0, len(piles) - 1, 2):            pile, count = merge(piles[k], piles[k + 1])            merged.append(pile)            comparisons = comparisons + count        if len(piles) % 2 == 1:            merged.append(piles[-1])        piles = merged    if len(piles) == 0:        return [], 0    return piles[0], comparisons print(merge_sort([62, 38, 85, 29, 91, 54, 70, 47]))print(merge_sort([5, 3, 5, 1, 4]))print(merge_sort([7]), merge_sort([]))

([29, 38, 47, 54, 62, 70, 85, 91], 17)([1, 3, 4, 5, 5], 8)([7], 0) ([], 0)

range(0, len(piles) - 1, 2) counts 0, 2, 4… so piles[k] and piles[k + 1] are each pair in turn. When the number of piles is odd, the last pile has no partner this round, and goes on to the next round as it is (len(piles) % 2 == 1). The edge tests matter: without the if len(piles) == 0 line, sorting an empty list would stop with an IndexError at piles[0].

Every algorithm in this unit so far is deterministic: given the same input, it takes the same steps and gives the same output, every time you run it. A calculator adding 245 + 378, a binary search, a merge sort: run them a thousand times, and nothing changes.

Some algorithms use chance on purpose: at some steps they choose at random, like rolling a die. They are called random (or randomized, or probabilistic) algorithms. Run one twice on the same input, and it may take different steps, and sometimes give a different answer. Why would anyone want that? Here are two reasons.

Chance can give a good answer quickly

What is π? Draw a square with sides of 1, and in it a quarter of a circle with radius 1. The square’s area is 1, and the quarter circle’s is π × 1² ÷ 4 = π ÷ 4. Now drop dots on the square at random places. About π ÷ 4 of them should land inside the quarter circle. So count them: 4 × (dots inside) ÷ (all dots) is about π.

Algorithms like this are called Monte Carlo methods. They are used where an exact answer would take far too long: forecasting the weather (many forecasts from slightly different starting points, to see how likely rain is), designing safer buildings, and planning how a disease might spread.

The same in Python, with Grade 8’s random module. random.random() gives a number from 0 up to (not including) 1, by chance:

import random random.seed(12)for dots in [100, 1000, 10000, 100000]:    inside = 0    for k in range(dots):        x = random.random()        y = random.random()        if x * x + y * y <= 1:            inside = inside + 1    print(dots, "dots: pi is about", 4 * inside / dots)

100 dots: pi is about 3.321000 dots: pi is about 3.1410000 dots: pi is about 3.1252100000 dots: pi is about 3.14136

A dot at (x, y) is inside the quarter circle when its distance from the corner is at most 1, that is, when x² + y² ≤ 1 (Pythagoras). More dots usually give a closer answer, but not always: here 1,000 dots happened to land closer to π (3.14159…) than 10,000 did.

What does random.seed(12) do? As Grade 7 said, a computer’s random numbers are pseudo-random: worked out by a formula from a starting number, the seed. Give the same seed, and the same “random” numbers come out, in the same order, every run. Run this program again and it prints exactly the same estimates. Delete the seed line and run it a few times: now each run starts from a different seed and gives different estimates. Programmers fix the seed while testing, so that a run can be repeated exactly when hunting a bug.

Chance can protect against bad luck

There is another fast sort, quicksort, which uses chance in a cleverer way. Here it is by hand, sorting a pile of marks:

1. Pick one mark from the pile: the pivot.
2. Compare every mark in the pile with the pivot, and split the pile into three: the marks smaller than the pivot, the pivot, and the marks bigger.
3. Now the three piles are in the right order, left to right. Do steps 1 and 2 again for every pile with more than one mark in it, until every pile has just one.

If the pivot is always somewhere near the middle, each round splits the piles roughly in half, and just as with merge sort, there are about log₂ n rounds of n comparisons each: O(n log n); written well, it is often even faster than merge sort in practice. But if the pivot is always the smallest mark, each round only takes that one mark off, and quicksort needs about n rounds: quadratic, as slow as bubble sort.

So which mark should be the pivot? The simplest rule is “the first in the pile”. But think what that does to a list that is already sorted: the first mark is always the smallest. A rule fixed in advance always has some input that fools it, and in real life, lists already in order (or nearly) are very common. The fix: pick the pivot at random. Then no input is bad every time; a slow run needs a long run of bad luck, which for big lists practically never happens.

import random def quick_sort(items, random_pivot):    """Sort by pivots, a round at a time; return the list and its looks."""    piles = [items]    looks = 0    done = False    while not done:        done = True        new_piles = []        for pile in piles:            if len(pile) <= 1:                new_piles.append(pile)                continue            done = False            if random_pivot:                pivot = random.choice(pile)            else:                pivot = pile[0]            smaller = []            same = []            bigger = []            for x in pile:                looks = looks + 1                if x < pivot:                    smaller.append(x)                elif x > pivot:                    bigger.append(x)                else:                    same.append(x)            new_piles.append(smaller)            for x in same:                new_piles.append([x])            new_piles.append(bigger)        piles = new_piles    result = []    for pile in piles:        for x in pile:            result.append(x)    return result, looks random.seed(9)in_order = list(range(1, 501))print("First as pivot: ", quick_sort(in_order, False)[1], "looks")for run in range(3):    answer, looks = quick_sort(in_order, True)    print("Random pivot:   ", looks, "looks", answer == in_order)

First as pivot:  125249 looksRandom pivot:    5110 looks TrueRandom pivot:    4844 looks TrueRandom pivot:    5051 looks True

looks counts each mark looked at and put on a pile, once per round. random.choice(pile) picks one item of a list by chance. continue (new here) skips the rest of the loop’s body and goes straight on to the next pile: a pile of one is finished, so there is nothing more to do with it. A mark equal to the pivot becomes a pile of its own, so equal marks can’t keep the loop going for ever.

On the 500 marks already in order, the first-as-pivot rule needs 125,249 looks: 500 + 499 + 498 + … + 2 (a pile of one is never looked at again), quadratic. The random pivot needs about 5,000, and a different number on each run. But look at the last column: the answer is the same, the correctly sorted list, every time. Random quicksort uses chance only to decide its work, never its answer. Monte Carlo used chance to decide its answer.

Deterministic or random?

Counting steps compares algorithms. But a real user waits seconds, not steps, and some steps take longer than others: a look in a dictionary is more work than a comparison of two numbers, although both count as one step. So programmers also time their programs, with a clock.

Python’s time module has a clock made for this: time.perf_counter() gives the time in seconds, very precisely, from some starting moment. Read it before and after the work; the difference is how long the work took.

import time for n in [100000, 200000, 400000]:    numbers = list(range(n))    book = {}    for x in numbers:        book[x] = True     start = time.perf_counter()    for k in range(100):        found = -1 in numbers    list_time = (time.perf_counter() - start) / 100     start = time.perf_counter()    for k in range(100000):        found = -1 in book    dict_time = (time.perf_counter() - start) / 100000     print(f"{n:>7} items: list {list_time * 1000:6.3f} ms, dictionary {dict_time * 1000:8.6f} ms")

The program searches for −1, which isn’t there: the worst case. in on a list is a linear search (Grade 8); in on a dictionary checks its keys by hashing (Unit 3). One search on its own is too quick to time well, so the list search is done 100 times and the dictionary search, far quicker, 100,000 times, and each total divided by the number of searches. * 1000 turns seconds into milliseconds (ms), thousandths of a second, and :6.3f prints 3 decimal places in 6 spaces. Press Run and compare your numbers with these, from one run on a laptop, in its browser:

Your times will be different, and they change each time you press Run, the tiny dictionary times most of all. But the pattern will be the same. The list’s time roughly doubles each time the list doubles: linear. The dictionary’s stays about the same, tiny, whatever its size: constant. That is Unit 3’s hashing, measured.

Two sorts on growing lists

Now the practical test of this unit: time insertion sort (Grade 8) and merge sort on lists of random marks, doubling the length each time, with Python’s own sorted() beside them.

import randomimport time def insertion_sort(items):    for k in range(1, len(items)):        j = k        while j > 0 and items[j - 1] > items[j]:            items[j - 1], items[j] = items[j], items[j - 1]            j = j - 1 def merge(a, b):    c = []    i = 0    j = 0    while i < len(a) and j < len(b):        if a[i] <= b[j]:            c.append(a[i])            i = i + 1        else:            c.append(b[j])            j = j + 1    return c + a[i:] + b[j:] def merge_sort(items):    piles = []    for x in items:        piles.append([x])    while len(piles) > 1:        merged = []        for k in range(0, len(piles) - 1, 2):            merged.append(merge(piles[k], piles[k + 1]))        if len(piles) % 2 == 1:            merged.append(piles[-1])        piles = merged    return piles[0] if piles else [] def seconds(sort, items, repeats):    """Time for one sort, on average, each on a new copy of the list."""    start = time.perf_counter()    for r in range(repeats):        sort(items.copy())    return (time.perf_counter() - start) / repeats print("  items  insertion    merge   sorted()")for n in [250, 500, 1000, 2000]:    marks = []    for k in range(n):        marks.append(random.randint(0, 100))    a = seconds(insertion_sort, marks, 3)    b = seconds(merge_sort, marks, 10)    c = seconds(sorted, marks, 1000)    print(f"{n:>7} {a * 1000:8.1f} ms {b * 1000:6.1f} ms {c * 1000:6.3f} ms")

One new idea: seconds(sort, items, repeats) takes a function as a parameter. In Python a function is a value like any other, so seconds(insertion_sort, marks, 3) hands the whole function to seconds, which calls it as sort(items.copy()). That lets one function time every sort, the same way, so the comparison is fair: each sort gets new copies of the same list, never one it has already sorted. The quicker the sort, the more times it is repeated, so that its time is long enough to measure: sorted() 1,000 times. (piles[0] if piles else [] is a short if–else in one line: piles[0] if there are any piles, otherwise an empty list.)

Here is one run, again on a laptop in its browser:

Each time the list doubles, insertion sort takes about 4 times as long (quadratic); merge sort a little over twice as long (n log n). The smaller the list, the closer the two: at 250 items merge sort was about 3 times as fast, at 2,000 items about 40 times, and the gap keeps growing. Python’s sorted() beats both by a long way: it is an n log n merge sort too, but written in C, a language whose programs run many times faster than Python’s, so each of its steps is much quicker. A better algorithm changes how the time grows; a faster language or computer only changes it by the same factor at every size.

After all this, a surprise: most of the time, a simple, slow algorithm is the right choice.

• The data is small. For 40 students, a quadratic algorithm makes 780 comparisons, done in well under a millisecond. Nobody will ever notice. The kinds of growth only matter when n gets big.
• It runs once. A program that tidies up one file once can take a minute; a program that a website runs for every visitor can’t.
• Clear code has fewer bugs. A clever algorithm is longer and harder to check. If the slow one is fast enough, the clear one is better: easier to test, to fix and to change.
• Your time counts too. An hour spent making a program a second faster is worth it if the program runs thousands of times a day, and not if it runs once.

Sometimes slowness is even what you want. In Unit 6, a website stores passwords with a slow hash, made slow on purpose so that guessing millions of passwords takes an attacker far too long; and encryption is safe because trying every key is exponential.

So, to choose an algorithm:

1. Make it correct first, with tests (ordinary, edge and wrong).
2. Ask how big the data will get, and how often the program runs.
3. Ask how the work grows with each algorithm you could use. If the data is big and an algorithm is quadratic or worse, look for a better plan: sorting first, a dictionary, merge sort, binary search.
4. Measure: count steps, or time it, on growing data.
5. Keep it clear: a function for each job, with a docstring, so that a better algorithm can later replace a slow one in one place.