Timing and counting comparisons in Python

Why this matters

Two sorts can look equally good on paper and still behave very differently in a program. One way to see the difference is to count the work a sort does. Another way is to measure how long it takes on a real computer. The two methods answer different questions.

Counting answers this question: how much work does the sort do on this input? The count is the same on every computer, because it depends only on the algorithm and the input. You can use counts to compare two sorts fairly, and to check a prediction by hand.

Timing answers a different question: how long does the user wait on this machine? The answer depends on the processor, the memory, the Python version and what else the computer is doing. A timing is useful for a decision only when it is measured carefully. A careless timing gives numbers that mislead.

This lesson uses the three simple sorts from the module's first lesson (bubble, selection and insertion) and Python's built-in sorted(). It does not explain why insertion sort is fast on nearly sorted data. The module has a separate lesson on that.

Words used in this lesson

A comparison is one question that asks whether one value is smaller than another.

A swap exchanges two values in a list. Insertion sort does not swap in the strict sense. It moves values one place to the right to make room, which the code below counts as a swap so the table has one column for moves.

A counter is a variable that goes up by one each time something happens. A counter for comparisons goes up each time the sort asks a question.

A benchmark is a test that measures how long a piece of code takes to run.

A median is the middle value of a list of numbers after sorting them. It is less affected by one unusually slow or fast run than the average is.

A nanosecond is one billionth of a second. time.perf_counter_ns() returns a time in nanoseconds, and the difference between two calls tells you how long the code between them took.

A warm-up run is a run of the code whose time is thrown away. Some languages compile code while the program runs, and the first runs are slow while that happens. Python's usual interpreter, CPython, does not compile your functions to machine code, so warm-up runs matter less in Python. The numbers in this lesson show how little they change.

Part 1: counting comparisons and swaps

The idea is simple. Put a counter inside the two operations that matter: the comparison and the swap. Every sort then increases the same counters.

The code keeps all comparisons in one helper called less. Each sort calls less instead of writing < directly. This way the counting is in one place, and no comparison can be forgotten.

class Work:
    def __init__(self):
        self.comparisons = 0
        self.swaps = 0
 
    def reset(self):
        self.comparisons = 0
        self.swaps = 0
 
    def __repr__(self):
        return f"comparisons={self.comparisons} swaps={self.swaps}"
 
def swap(a, i, j, w):
    a[i], a[j] = a[j], a[i]
    w.swaps += 1
 
def less(x, y, w):
    w.comparisons += 1
    return x < y

The Work class holds the two counts. The reset method sets both counts back to zero, so one object can be used for several sorts. The __repr__ method is the text that Python prints when you show the object, so print(w) gives the counts on one line.

The less helper takes the Work object as its third argument. If you leave that argument out, Python stops with an error. The mistakes section shows the message.

Here is bubble sort with the counters added. It is the same algorithm as in the module's first lesson, plus the counting.

def bubble_sort(a, w):
    for pass_number in range(len(a) - 1):
        swapped = False
        for i in range(len(a) - 1 - pass_number):
            if less(a[i + 1], a[i], w):
                swap(a, i, i + 1, w)
                swapped = True
        if not swapped:
            break

Read the if line carefully. It asks whether the right value is smaller than the left value. If so, the two are in the wrong order, and the code swaps them. The break at the end is an early exit. If a whole pass makes no swap, the list is already sorted, so the outer loop can stop.

Insertion sort and selection sort use the same two helpers. Insertion sort counts each shift as a swap, because each shift is one write that moves a value out of the way.

def insertion_sort(a, w):
    for i in range(1, len(a)):
        value = a[i]
        j = i - 1
        while j >= 0 and less(value, a[j], w):
            a[j + 1] = a[j]
            w.swaps += 1
            j -= 1
        a[j + 1] = value
 
def selection_sort(a, w):
    for i in range(len(a) - 1):
        smallest = i
        for j in range(i + 1, len(a)):
            if less(a[j], a[smallest], w):
                smallest = j
        if smallest != i:
            swap(a, i, smallest, w)

The built-in sorted() cannot be counted directly, because it does not call our helpers. There is a way around this. sorted accepts a key function, and a comparison function can be turned into a key with functools.cmp_to_key. The comparison function answers the question "which of these two comes first?" with a negative number, zero or a positive number. If that function counts its own calls, the count is the number of comparisons that sorted made.

from functools import cmp_to_key
 
def library_counted_sort(a, w):
    def cmp(x, y):
        w.comparisons += 1
        return (x > y) - (x < y)
    a[:] = sorted(a, key=cmp_to_key(cmp))

The expression (x > y) - (x < y) gives 1, -1 or 0, which is the sign the sort expects. The line a[:] = ... writes the sorted items back into the same list, so the caller sees the result, as the other sorts do.

Running the counts on a small input

The first run uses eight numbers. Small inputs let you check the counts by hand. The report function runs each sort on its own copy of the input, prints the counts, and checks that the result is correct.

The output is:

input: [5, 2, 9, 1, 7, 3, 8, 4]
bubble     comparisons=25 swaps=13  correct=True
selection  comparisons=28 swaps=5  correct=True
insertion  comparisons=18 swaps=13  correct=True
library    comparisons=17 swaps=0  correct=True

Look at the bubble and insertion swap counts, which are both 13. This is not a coincidence. An inversion is a pair of values that are in the wrong order, with the bigger one before the smaller one. Each swap of two neighbours removes exactly one inversion, and the sort is finished when there are none left. So bubble sort and insertion sort both make exactly as many swaps as the input has inversions.

Selection sort makes at most one swap per position, so its swap count is small (5 here). Its comparison count is 28 for eight values. This is always n times (n minus 1) divided by 2 comparisons, where n is the number of values. That formula is 8 times 7 divided by 2, which is 28.

The built-in sorted() makes only 17 comparisons. It is far fewer than the simple sorts, because it does not compare every pair of neighbours. Its swap count is 0 in the table, because sorted moves values with its own code, and that code is not counted. The 0 does not mean the sort does no moves. It means the table does not count them.

Running the counts on 100 numbers

Eight numbers are too few to show the trend. The next run uses 100 numbers. The random_array function fills a list with random numbers from 0 to 99, using a fixed seed. A seed is the starting number for a random number generator. With the same seed, the same numbers come out every time, so you can repeat the run.

The run below also checks the two special inputs: a list that is already sorted, and a list in reverse order.

The output is:

random input, 100 numbers, seed 3
bubble     comparisons=4914 swaps=2420  correct=True
selection  comparisons=4950 swaps=95  correct=True
insertion  comparisons=2516 swaps=2420  correct=True
library    comparisons=530 swaps=0  correct=True
special inputs, 100 numbers
sorted    bubble     comparisons=99 swaps=0
sorted    selection  comparisons=4950 swaps=0
sorted    insertion  comparisons=99 swaps=0
reversed  bubble     comparisons=4950 swaps=4950
reversed  selection  comparisons=4950 swaps=50
reversed  insertion  comparisons=4950 swaps=4950

Three patterns stand out.

Bubble sort and insertion sort do much less work on sorted input. Bubble sort stops after one pass, because that pass makes no swap. Insertion sort checks each value once against the value just before it, and stops. Selection sort does not have that shortcut. It always makes all 4950 comparisons, even when the input is sorted.

On reversed input, bubble sort and insertion sort reach their worst case. Every pair is an inversion, so every pair needs a swap. For 100 values, there are 4950 pairs, which is why both counts are 4950.

On random input, the simple sorts make a number of comparisons that grows with the square of the list length. The built-in sort made 530 comparisons for 100 values, which is much less. The exact count can differ on another Python version. It does not compare every pair. This lesson does not explain how it avoids them.

Part 2: timing a sort

Counting tells you about the algorithm. Timing tells you about the program on your machine. To time a sort, you need four habits.

The first habit is to start a clock right before the sort and stop it right after. In Python, time.perf_counter_ns() gives the time in nanoseconds. Subtracting the start from the end gives the elapsed time.

The second habit is to give each run the same input. A sort changes the list it is given. If you sort the list once and then sort it again, the second sort works on a list that is already sorted. So each timed run copies the input first.

The third habit is to run the sort several times and report more than one number. The median is the value in the middle after sorting the times. The fastest run is also useful, because it shows the sort's best case on this machine without interference from other programs.

The fourth habit is to run some warm-up runs before the timed runs. In Python the effect is small, but the habit costs nothing, and other languages need it.

Here is a timing program that follows those habits. It times the two simple sorts from Part 1 without the counter, so the timing measures only the sort.

import random
import statistics
import time
 
def bubble_sort(a):
    for pass_number in range(len(a) - 1):
        swapped = False
        for i in range(len(a) - 1 - pass_number):
            if a[i + 1] < a[i]:
                a[i], a[i + 1] = a[i + 1], a[i]
                swapped = True
        if not swapped:
            break
 
def insertion_sort(a):
    for i in range(1, len(a)):
        value = a[i]
        j = i - 1
        while j >= 0 and value < a[j]:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = value
 
def random_array(n, seed):
    rng = random.Random(seed)
    return [rng.randrange(100) for _ in range(n)]
 
def time_one_run(fn, data):
    copy = list(data)                    # a fresh copy, made before the clock starts
    start = time.perf_counter_ns()
    fn(copy)
    return time.perf_counter_ns() - start
 
def measure(name, fn, data, warm_runs, timed_runs):
    for _ in range(warm_runs):
        time_one_run(fn, data)
    times = [time_one_run(fn, data) for _ in range(timed_runs)]
    times.sort()
    print(f"{name:<10} warm-up runs={warm_runs}  fastest={times[0] / 1e6:8.3f} ms  "
          f"median={statistics.median(times) / 1e6:8.3f} ms")
 
n = 5000
data = random_array(n, 7)
print(f"n = {n}, same random input for every run")
print(f"first bubble run, no warm-up: {time_one_run(bubble_sort, data) / 1e6:.3f} ms")
measure("bubble", bubble_sort, data, 0, 5)
measure("bubble", bubble_sort, data, 5, 5)
measure("insertion", insertion_sort, data, 0, 5)
measure("insertion", insertion_sort, data, 5, 5)

time_one_run makes a fresh copy of the input before it starts the clock. The copy is made outside the timed part, so only the sort is measured. The function returns the elapsed time in nanoseconds.

measure does the warm-up runs first, then the timed runs. It stores the times in a list, sorts the list of times, and prints the fastest value and the median. The number 1e6 converts nanoseconds to milliseconds. The format :8.3f prints the number with three decimal places in a field eight characters wide.

The output of one run on a WSL2 Linux machine with Python 3.14 was:

n = 5000, same random input for every run
first bubble run, no warm-up: 481.775 ms
bubble     warm-up runs=0  fastest= 480.099 ms  median= 481.614 ms
bubble     warm-up runs=5  fastest= 475.290 ms  median= 483.288 ms
insertion  warm-up runs=0  fastest= 201.045 ms  median= 204.922 ms
insertion  warm-up runs=5  fastest= 198.371 ms  median= 209.642 ms

Your numbers will be different. The exact values depend on your processor and on what else is running. Read the pattern, not the digits.

The warm-up runs make almost no difference here. The median with five warm-up runs is close to the median with none, for both sorts. This is what you expect from CPython, which runs the same code the same way every time. The result that matters is the gap between the sorts. Insertion sort is about twice as fast as bubble sort on this random input, and the counts from Part 1 point the same way. Insertion sort made fewer comparisons than bubble sort on random input, and the same number of swaps. Counts alone do not explain the whole gap, so use them as a guide to the timing and measure before you trust a claim.

Common mistakes

Mistake 1: reusing the input list between runs

A beginner often writes this:

start = time.perf_counter_ns()
bubble_sort(data)
elapsed = time.perf_counter_ns() - start

Then they run the same code again on data. The first run sorts data. The second run sorts a list that is already sorted. The timing becomes meaningless.

The counts from Part 1 show how big the effect can be. On sorted input, bubble sort makes 99 comparisons and no swaps. On random input of 100 values, it made 4914 comparisons and 2420 swaps. A repeated run on the same list measures the sorted case, not the random case. The next program shows the difference on 5000 numbers:

The output is:

second run on a sorted list runs in under 1 ms: True

The second call does one pass over the list and stops, so the time is far below the random case. Copy the input before every run, as time_one_run does.

Mistake 2: timing one run and trusting it

A single timing includes the cold start and any other program on the computer that happens to be busy at that moment. The first bubble run in the output above took 481.775 ms, and the other runs were close to that value. A single run can still be far off, because the operating system may pause the program for a moment. Those two numbers describe the same algorithm on the same input, but one of them can be unlucky.

Run several times, take the median, and say how many runs you took.

Mistake 3: printing inside the timed part

A line like print(...) inside the timed section adds the time spent writing text to the console. That time is usually larger than the time the sort takes on a small input. Put the printing after the second call to time.perf_counter_ns(), as the program does.

Mistake 4: a clock with too coarse a unit

time.time() returns the time in seconds as a decimal number, and its resolution depends on the system. A sort on 10 numbers can finish in much less than one millisecond. Measured with a coarse clock, it can look like it took zero time. Use time.perf_counter_ns(), which is built for measuring short intervals, and time the sort many times in a loop. The timeit module from the standard library does the repeats for you.

Mistake 5: forgetting the counter in one place

If you count comparisons in some loops and forget others, the total is wrong. Calling less for every comparison is the simplest way to avoid this. The helper also makes the program easier to read, because every comparison in the code looks the same.

Mistake 6: calling a helper without its counter

The less helper needs the Work object. This program leaves it out:

The output is:

Traceback (most recent call last):
  File "count_err.py", line 6, in <module>
    if less(a[1], a[0]):
       ~~~~^^^^^^^^^^^^
TypeError: less() missing 1 required positional argument: 'w'

The message says the function less needs one more argument, named w. Add the missing argument, as in less(a[1], a[0], w). The first line of the traceback names the file, which depends on where you saved the program.

Practice

Try each exercise in a file first. Check your answer after you have made an attempt.

Exercise 1

Selection sort on a list of 6 values always makes the same number of comparisons, no matter what the values are. How many is it?

Show the answer

The answer is 15. The formula is n times (n minus 1) divided by 2. Here n is 6, so the count is 6 times 5 divided by 2, which is 15. Running the counting code on an input of six values gave 15 comparisons.

Exercise 2

Predict the number of comparisons and swaps that bubble sort makes on [3, 2, 1] with the early exit in place.

Show the answer

The answer is 3 comparisons and 3 swaps. The three pairs are (3, 2), (3, 1) and (2, 1). All three are inversions, so there are 3 swaps. Pass 0 compares two pairs, and pass 1 compares one pair. Pass 1 makes a swap, so the code does not stop early. The loop then stops because the pass count reaches 2. The total is 2 plus 1, which is 3 comparisons. Running the counting code gave 3 comparisons and 3 swaps.

Exercise 3

Predict the number of comparisons and swaps that insertion sort makes on [2, 1, 4, 3].

Show the answer

The answer is 4 comparisons and 2 swaps. Insertion sort first moves 1 in front of 2, which is one comparison and one shift. Then 4 is compared with 2 and stays in place, one comparison. Then 3 is compared with 4 and shifted in front of it, and then compared with 2 and stays after it, two comparisons and one shift. The total is 1 plus 1 plus 2, which is 4 comparisons. There are 2 shifts. Running the counting code gave 4 comparisons and 2 swaps.

Exercise 4

Bubble sort is run on the already sorted list [0, 1, 2, ..., 9] with the early exit in place. How many comparisons does it make, and how many swaps?

Show the answer

The answer is 9 comparisons and 0 swaps. The first pass compares 9 neighbouring pairs and makes no swap. Because the pass had no swap, the code breaks out of the loop. Running the counting code gave 9 comparisons and 0 swaps.

Exercise 5

A student wrote this timing code and reported that bubble sort takes 0.4 ms on 5000 numbers. List three things that make the number unreliable, and say how to fix each one.

data = random_array(5000, 7)
start = time.perf_counter_ns()
bubble_sort(data)
print("took", (time.perf_counter_ns() - start) / 1e6, "ms")

Show the answer

The first problem is that the run is a single run, with no median and no number of runs given. Take several timed runs and report the median and how many runs it came from. The second problem is that the list is sorted in place, so any repeat would sort an already sorted list. Copy the input before each run. The third problem is the size of the number: 0.4 ms is too small for a sort of 5000 random numbers, which takes hundreds of milliseconds in this lesson. A time that short usually means the sort did little work, for example because the input was already sorted. Check the input before you trust the time.

Summary

• Count comparisons and swaps with a helper such as less and a Work object, so every comparison is counted in one place.
• Counts are the same on every computer, so they are good for predicting work and comparing sorts. Insertion sort and bubble sort make as many swaps as the input has inversions.
• Measure time with time.perf_counter_ns(), a fresh copy of the input for each run, several timed runs, and the median.
• A single timing is unreliable, and a repeat on the same list measures a different case from the one you intended.
• Python's built-in sorted() makes far fewer comparisons than the simple sorts, and its time for the same input is much lower.