How It Works: Step-by-Step Traces

This chapter traces four algorithms by hand on small inputs: merge sort, counting inversions during the merge, fast exponentiation and quickselect. Working through the traces once makes the code in the next chapter easy to follow.

Merge sort on eight numbers

Take [5, 2, 4, 7, 1, 3, 2, 6]. The array is cut in half until every piece holds one element, then the pieces are merged back level by level.

Every level touches each element once, and there are log2 8 = 3 levels: that is where O(n log n) comes from. The merge compares the front elements of two sorted lists and repeatedly takes the smaller one.

def merge(left, right):
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:    # <= keeps equal elements in order (stable)
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    out.extend(left[i:])
    out.extend(right[j:])
    return out

print(merge([2, 4, 5, 7], [1, 2, 3, 6]))  # [1, 2, 2, 3, 4, 5, 6, 7]

Counting inversions during the merge

An inversion is a pair of positions i < j with a[i] > a[j]. Checking every pair costs O(n^2). Divide and conquer sorts inversions into three kinds: both elements in the left half, both in the right half, or one on each side (crossing). The first two kinds are counted recursively. Crossing pairs come almost for free during the merge: when right[j] is taken before left[i], it is smaller than left[i] and every element after it in the left list, so it forms len(left) - i crossing inversions.

The final merge of the trace above, [2, 4, 5, 7] with [1, 2, 3, 6]:

The final merge adds 11. The lower levels add 1 for [5] with [2], 1 for [2, 5] with [4, 7] (4 is less than 5) and 1 for [1, 3] with [2, 6] (2 is less than 3). The array therefore has 14 inversions. Because the tie 2 <= 2 takes the left element first, equal values are never counted.

Fast exponentiation

Multiplying b by itself e - 1 times is hopeless when e is large. Halve the exponent instead: b^e = (b^(e/2))^2 when e is even, and b^e = (b^((e-1)/2))^2 * b when e is odd. Each call halves e, so at most about 2 log2 e multiplications are needed.

Trace for 3^13 (13 is 1101 in binary):

def power(b, e):
    if e == 0:
        return 1
    half = power(b, e // 2)
    return half * half * b if e % 2 else half * half

print(power(3, 13))  # 1594323

Five calls replace twelve multiplications; for e = 10^18 it is about 60 calls instead of 10^18 steps.

Quickselect

Quickselect finds the k-th smallest element (0-based) without sorting everything. It partitions around a pivot as quicksort does, then continues only in the side that contains position k.

Trace with the last element as pivot, a = [7, 2, 9, 4, 1, 8, 3], k = 3:

After the first step each partition peels off a single element. That is exactly how the O(n^2) worst case arises with a poor pivot. A random pivot makes long runs like this unlikely and gives O(n) expected time.

import random

def quickselect(a, k):
    """k-th smallest (0-based) element of a; reorders a in place."""
    lo, hi = 0, len(a) - 1
    while lo < hi:
        p = random.randint(lo, hi)        # random pivot
        a[p], a[hi] = a[hi], a[p]
        pivot, store = a[hi], lo
        for i in range(lo, hi):           # Lomuto partition
            if a[i] < pivot:
                a[i], a[store] = a[store], a[i]
                store += 1
        a[store], a[hi] = a[hi], a[store]
        if k == store:
            return a[k]
        if k < store:
            hi = store - 1
        else:
            lo = store + 1
    return a[k]

print(quickselect([7, 2, 9, 4, 1, 8, 3], 3))  # 4

Summary

• Merge sort does its real work in the merge: log n levels of O(n) work each.
• Crossing inversions are counted with len(left) - i whenever the right side wins.
• Fast exponentiation halves the exponent and needs only O(log e) multiplications.
• Quickselect continues in one side only; random pivots keep it at O(n) expected time.