Comparison of Sorting Algorithms using Python Decorators

I wrote this exercise while learning Python decorators and sorting algorithms. The goal was to time an operation without putting timing code inside every algorithm.

Technical revision — October 2026: the original decorator skipped recursive calls in MergeSort, and SelectionSort swapped elements outside its outer loop. Those implementations did not reliably sort the input, so their published timings were not a valid comparison. The corrected example below checks every result against Python’s sorted before reporting a measurement.

Time the outer operation

A decorator wraps a function and can add behavior around its execution. Here, timed returns the function’s result and its elapsed time in seconds, measured with perf_counter. This intentionally changes the return contract to a pair; a timing decorator is not automatically transparent to its caller.

MergeSort uses an undecorated recursive helper. Every recursive call executes normally, while the decorator times the complete outer operation once. SelectionSort swaps inside the outer loop, after finding the minimum of the remaining suffix. All three implementations modify the supplied list in place.

Corrected example

Download sorting.py. It uses only the Python standard library.

sorting.pypython · 80 linesDownload
Expand sourceCollapse source 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
"""Correctness first: time the outer call, not recursive subproblems."""

from functools import wraps
from random import Random
from statistics import median
from time import perf_counter
import platform


def timed(function):
    @wraps(function)
    def wrapper(*args, **kwargs):
        start = perf_counter()
        result = function(*args, **kwargs)
        return result, perf_counter() - start
    return wrapper


@timed
def merge_sort(values):
    def sort(items):
        if len(items) < 2:
            return
        middle = len(items) // 2
        left, right = items[:middle], items[middle:]
        sort(left)
        sort(right)
        i = j = k = 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                items[k] = left[i]
                i += 1
            else:
                items[k] = right[j]
                j += 1
            k += 1
        items[k:] = left[i:] + right[j:]
    sort(values)


@timed
def selection_sort(values):
    for i in range(len(values)):
        minimum = i
        for j in range(i + 1, len(values)):
            if values[j] < values[minimum]:
                minimum = j
        values[i], values[minimum] = values[minimum], values[i]


@timed
def bubble_sort(values):
    for end in range(len(values) - 1, 0, -1):
        swapped = False
        for i in range(end):
            if values[i] > values[i + 1]:
                values[i], values[i + 1] = values[i + 1], values[i]
                swapped = True
        if not swapped:
            break


def benchmark(size=1000, repeats=5, seed=42):
    original = Random(seed).sample(range(size * 10), size)
    expected = sorted(original)
    print(f"Python {platform.python_version()} | {platform.system()} {platform.machine()}")
    print(f"{size} distinct integers | seed={seed} | {repeats} repetitions | median ms")
    for algorithm in (merge_sort, selection_sort, bubble_sort):
        samples = []
        for _ in range(repeats):
            values = original.copy()  # Copying is outside the timed section.
            _, elapsed = algorithm(values)
            if values != expected:
                raise AssertionError(f"{algorithm.__name__} did not sort correctly")
            samples.append(elapsed * 1000)
        print(f"{algorithm.__name__}: {median(samples):.3f}")


if __name__ == "__main__":
    benchmark()

Run it with:

Source codebash
1
python sorting.py

Reading the measurements

The benchmark uses 1,000 distinct integers generated with seed 42, five repetitions per algorithm, and reports the median elapsed time. Each run starts with a fresh copy of the same list. Copying the input and verifying the result happen outside the timed section. The output records the Python version and operating-system architecture.

These timings describe this implementation and this input on the machine running it. They are not a universal ranking: already sorted inputs, duplicates, interpreter versions and machine load affect measurements. Before drawing performance conclusions, repeat the comparison across those cases and include Python’s built-in sort as a practical baseline.

For these implementations, MergeSort takes O(n log n) time and O(n) auxiliary storage; SelectionSort takes O(n²) time. BubbleSort takes O(n²) in the worst case and stops early when a pass makes no swaps.

The original invalid benchmark results have been removed. The executable example generates new measurements and refuses to report a timing for an incorrect result.

Time the outer operation

Corrected example

Reading the measurements

References