Sorting

Why sort

Sorted data is easier to use. Binary search (last lesson) needs it. Duplicates end up next to each other, which is why the Shell course runs sort before uniq. The smallest, largest, median, and top ten are all a slice away. Sorting is so useful that it’s the most studied problem in computing, and a good place to see how much an algorithm’s design matters.

Insertion sort

Insertion sort is how most people sort a hand of cards: take each item in turn and slide it left past the bigger ones until it’s in place among the items already sorted. It’s simple and does well on lists that are nearly sorted already, since little has to slide. But on random data each new item slides past about half of the sorted ones, so the comparisons add up to about n²/4: O(n²).

Merge sort

Merge sort is the classic example of divide and conquer: if the list has one item or none, it’s already sorted; otherwise, split it into two halves, sort each half with merge sort, and merge the two sorted halves into one ¹. A function that calls itself on a smaller version of its own problem, like this, is recursive.

Merging is the easy part: look at the front item of each half, take the smaller, and repeat. Each comparison places one item, so merging n items takes at most n comparisons. Halving the list again and again reaches single items after about log₂ n levels, and each level merges all n items, so merge sort makes at most n log₂ n comparisons: O(n log n) ¹.

Measuring them

This program implements both, counts their comparisons, checks the results against Python’s own sorted(), and times all three on random numbers. Save it as sorts.py:

# sorts.py: insertion sort and merge sort, counted and timed against Python's sorted().
import random
import time

def insertion_sort(a):
    """Take each item in turn and slide it left into place among the sorted ones."""
    a = a[:]
    comparisons = 0
    for i in range(1, len(a)):
        item = a[i]
        j = i - 1
        while j >= 0:
            comparisons += 1
            if a[j] <= item:
                break
            a[j + 1] = a[j]             # shift the bigger item one place right
            j -= 1
        a[j + 1] = item
    return a, comparisons

def merge_sort(a):
    """Sort each half, then merge the two sorted halves."""
    if len(a) <= 1:
        return a, 0
    mid = len(a) // 2
    left, c1 = merge_sort(a[:mid])
    right, c2 = merge_sort(a[mid:])
    merged, i, j, comparisons = [], 0, 0, c1 + c2
    while i < len(left) and j < len(right):
        comparisons += 1
        if left[i] <= right[j]:         # take the smaller front item
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged += left[i:] + right[j:]      # one side is used up; the rest is in order
    return merged, comparisons

if __name__ == "__main__":
    random.seed(2)
    for n in (1_000, 2_000, 4_000):
        data = [random.random() for _ in range(n)]
        for name, sort in [("insertion sort", insertion_sort), ("merge sort", merge_sort)]:
            start = time.perf_counter()
            result, comparisons = sort(data)
            elapsed = time.perf_counter() - start
            assert result == sorted(data)
            print(f"n={n:<6,} {name:<15} {comparisons:>10,} comparisons  {elapsed:8.4f} s")
        start = time.perf_counter()
        sorted(data)
        print(f"n={n:<6,} {'sorted()':<15} {'':>22}  {time.perf_counter() - start:8.4f} s")

assert stops the program with an error if its condition is false, a cheap way to check that a sort really sorted. The if __name__ == "__main__": line runs the measurements only when the file is run directly, so next lesson can import the two functions without running them.

On a desktop PC:

me@linuxbox:~$ python3 sorts.py
n=1,000  insertion sort     251,307 comparisons    0.0109 s
n=1,000  merge sort           8,718 comparisons    0.0009 s
n=1,000  sorted()                                  0.0000 s
n=2,000  insertion sort   1,004,402 comparisons    0.0444 s
n=2,000  merge sort          19,434 comparisons    0.0018 s
n=2,000  sorted()                                  0.0001 s
n=4,000  insertion sort   3,977,281 comparisons    0.1934 s
n=4,000  merge sort          42,852 comparisons    0.0040 s
n=4,000  sorted()                                  0.0002 s

The doubling test from last lesson, in action: each time n doubles, insertion sort’s comparisons quadruple (very close to n²/4), while merge sort’s only slightly more than double. At 4,000 items merge sort is already about fifty times faster, and the gap keeps widening. Python’s built-in sorted() is faster still: the same idea, written in C and tuned for years.

The n log n limit

Can a cleverer comparison sort beat n log n? No. A list of n distinct items can be in any of n! (n factorial) orders, and a sort has to tell them all apart. Each comparison has only two outcomes, so k comparisons can distinguish at most 2^k cases; telling n! cases apart needs at least log₂(n!) comparisons, which is about n log₂ n. Any sort that learns about the items only by comparing them needs that many on some inputs, and on average for random ones ¹. Merge sort is within a small constant of the best possible.

The limit applies only to comparing. If the items are small integers, say ages from 0 to 120, counting sort just counts how many of each value there are and writes them back out in order, in O(n + k) time for values below k, with no comparisons at all ¹.

Python’s sort

Python’s list.sort() and sorted() use an adaptive, stable, natural merge sort ². It scans the list for runs, stretches that are already in order (reversing descending ones), extends short runs to a minimum length with insertion sort, and then merges the runs ². On random data it’s an ordinary merge sort; on data with order already in it, it can need as few as n − 1 comparisons ^{2 3}.

You can count its comparisons by sorting objects that count each time they’re compared; Python’s sort compares only with < ⁴. Save this as adaptive.py:

# adaptive.py: count the comparisons Python's own sort makes on different inputs.
import math
import random

class Counted:
    comparisons = 0

    def __init__(self, value):
        self.value = value

    def __lt__(self, other):            # Python's sort only ever compares with <
        Counted.comparisons += 1
        return self.value < other.value

n = 100_000
random.seed(3)
inputs = {
    "random order": random.sample(range(n), n),
    "already sorted": list(range(n)),
    "reversed": list(range(n, 0, -1)),
}
for name, values in inputs.items():
    Counted.comparisons = 0
    sorted(Counted(v) for v in values)
    print(f"{name:<15} {Counted.comparisons:>9,} comparisons")
print(f"log2(n!), the minimum for random order: {math.lgamma(n + 1) / math.log(2):,.0f}")

__lt__ is the method Python calls for <; defining it lets a class be sorted. math.lgamma(n + 1) is the natural log of n!, computed without building the enormous number itself.

me@linuxbox:~$ python3 adaptive.py
random order    1,529,208 comparisons
already sorted     99,999 comparisons
reversed           99,999 comparisons
log2(n!), the minimum for random order: 1,516,704

On random data, within 1% of the theoretical minimum. On sorted or reversed data, one pass: 99,999 comparisons for 100,000 items.

Two more things to know ⁴:

• It’s stable: items that compare equal keep their original order. So to sort by two things, sort by the less important one first, then by the more important one.
• It takes a key function, applied to each item before comparing: sorted(words, key=len) sorts by length, sorted(names, key=str.casefold) ignores case, and a key that returns a tuple, such as key=lambda w: (len(w), w), sorts by length and then alphabetically.

Your turn

So

Insertion sort slides each item into place: simple, quick on nearly sorted data, but O(n²), its comparisons quadrupling as the input doubles. Merge sort splits, sorts the halves recursively, and merges, in at most n log₂ n comparisons, and no sort that only compares items can do better than about log₂(n!) ≈ n log₂ n. Counting sort escapes the limit by not comparing at all. Python’s sort is an adaptive, stable merge sort that exploits order already present (99,999 comparisons for 100,000 sorted items) and accepts key functions.