We compare all the sorts we have written on four kinds of input and derive selection rules. We measure the number of comparisons, not seconds: it does not depend on the computer and is identical on every run. The sorts themselves come from earlier lessons: bubble, insertion, merge, quick, heap, Timsort.

Comparison counts of six sorts on four kinds of input
Comparison counts of six sorts on four kinds of input

Why count, not time

Seconds from timeit depend on the machine, the Python version and the load, and change from run to run. The number of comparisons is a property of the algorithm. We wrap every item in a class Key whose __lt__ counts calls: every sort that uses < is measured with the same counter. Real time is still worth checking separately with timeit.

python
import random, heapq

class Key:
    count = 0
    def __init__(self, v): self.v = v
    def __lt__(self, other):
        Key.count += 1
        return self.v < other.v