Sorting

Why sorting matters, stability, and in-place

Imagine a library whose books are shelved randomly. Finding one book means checking every shelf. Shelve them by author and you can jump straight to the right spot (binary search, M30), see all books by one author side by side (grouping), and spot duplicates because they are now neighbors. Sorting is a preprocessing step that makes many other problems cheap.

Two properties describe how a sorting algorithm behaves beyond speed:

Throughout this module, n is the number of items, and we count comparisons and moves (swaps or writes), because those dominate the cost. Watch the counters in the visualizer as you try different algorithms on the same data:

Remember: stable means equal keys keep their order; in-place means O(1) or O(log n) extra memory. Python's built-in sort is stable but not in-place in the strict sense (it may use up to n/2 extra pointers).

Bubble, selection, and insertion sort

These three O(n²) algorithms are too slow for large inputs, but they are the clearest place to learn the most important skill in this module: proving a sort correct with a loop invariant. An invariant is a statement that is true before every iteration of a loop. If it holds at the start, every iteration preserves it, and it implies "sorted" when the loop ends, the algorithm is correct.

Bubble sort

Intuition: bubbles rise. Walk through the list swapping each adjacent pair that is out of order; the largest item "bubbles" to the end. Repeat on the shorter unsorted part.

for end from n-1 down to 1:
    swapped = False
    for i in 0 .. end-1:
        if a[i] > a[i+1]: swap them; swapped = True
    if not swapped: stop          # already sorted: best case O(n)

Invariant: after pass k, the last k positions hold the k largest items in their final sorted order. Cost: worst and average O(n²) comparisons and swaps; best O(n) with the early exit; O(1) space; stable (it only swaps strictly greater neighbors).

Selection sort

Intuition: picking a sports team. Scan everyone, pick the best, put them first; scan the rest, pick the next best, and so on.

for i in 0 .. n-2:
    m = index of the minimum of a[i..n-1]
    swap a[i], a[m]

Invariant: a[0:i] holds the i smallest items, sorted, and every item in a[i:] is at least as large as each of them. Cost: always Θ(n²) comparisons, even on sorted input, but only n − 1 swaps, which matters when writes are expensive (flash memory). O(1) space. Not stable: the long-distance swap can jump an item past an equal one.

Insertion sort

Intuition: sorting a hand of cards. Pick up cards one at a time and slide each one left into its place among the cards you already hold.

for i in 1 .. n-1:
    item = a[i]; j = i - 1
    while j >= 0 and a[j] > item:
        a[j+1] = a[j]; j -= 1     # shift bigger items right
    a[j+1] = item

Invariant: before iteration i, a[0:i] contains the original first i items in sorted order. Cost: worst O(n²) (reverse-sorted input), best O(n) (already sorted), and in general O(n + inversions), where an inversion is a pair that is out of order. That makes insertion sort the champion for small or nearly sorted inputs, which is why Timsort uses it internally. O(1) space, stable.

Remember: insertion sort is O(n + inversions) and stable; selection sort minimizes swaps; bubble sort is mainly a teaching tool.

Merge sort

Intuition: two people each sort half a stack of exam papers, then merge their piles by repeatedly taking whichever top paper comes first. Merging two sorted piles is easy and linear; recursion makes the halves sorted. You previewed this in M28.

merge_sort(a):
    if len(a) <= 1: return a
    mid = len(a) // 2
    return merge(merge_sort(a[:mid]), merge_sort(a[mid:]))

merge(L, R):
    out = []; i = j = 0
    while i < len(L) and j < len(R):
        if R[j] < L[i]: out.append(R[j]); j += 1
        else:           out.append(L[i]); i += 1    # ties take from L: stable
    append the leftovers of L and R
    return out

Merge invariant: out holds the i + j smallest items of L + R in sorted order, and L[i] and R[j] are the smallest remaining items of each list. Taking the smaller of the two keeps the invariant. Stability: on a tie we take from the left, so equal items keep their order.

Complexity: T(n) = 2T(n/2) + Θ(n) = Θ(n log n) in the best, average, and worst case. Space: Θ(n) for the merge buffer plus O(log n) stack. When to use: when you need guaranteed n log n and stability, for linked lists (merging needs no random access), and for data on disk (external sorting, this module's mini-project).

Remember: merge sort is predictable and stable; its price is O(n) extra memory.

Quicksort

Intuition: a teacher lines up a class by height. Pick one student (the pivot); everyone shorter goes to the left, everyone taller to the right. The pivot is now exactly where they belong. Repeat in each group. All the work happens in the split (the partition); there is no merge step.

quicksort(a, lo, hi):
    if lo >= hi: return
    p = partition(a, lo, hi)      # pivot ends at index p
    quicksort(a, lo, p - 1)
    quicksort(a, p + 1, hi)

Lomuto vs Hoare partitioning

def lomuto(a: list[int], lo: int, hi: int) -> int:
    pivot = a[hi]
    i = lo                           # a[lo:i] < pivot, a[i:j] >= pivot
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]        # put the pivot between the two parts
    return i

def hoare(a: list[int], lo: int, hi: int) -> int:
    pivot = a[(lo + hi) // 2]
    i, j = lo - 1, hi + 1
    while True:
        i += 1
        while a[i] < pivot: i += 1
        j -= 1
        while a[j] > pivot: j -= 1
        if i >= j:
            return j                 # recurse on [lo, j] and [j+1, hi]
        a[i], a[j] = a[j], a[i]

Worst case, pivot choice, and randomization

If the pivot is always the smallest or largest item (for example, the last item of an already sorted list with Lomuto), one side is empty and the other has n − 1 items: T(n) = T(n − 1) + Θ(n) = Θ(n²), with Θ(n) recursion depth. Defenses:

• Random pivot: swap a random element into the pivot position. The expected time is O(n log n) for every input; no adversary can force the bad case reliably.
• Median of three: use the median of the first, middle, and last items. Cheap and fixes sorted input, though crafted inputs can still defeat it.
• Recurse on the smaller side first and loop on the larger: stack depth becomes O(log n).
• Introsort (C++ std::sort) switches to heapsort if recursion gets too deep, guaranteeing O(n log n).

Three-way partitioning

When there are many duplicates (sorting a million survey answers rated 1 to 5), split into three groups: < pivot, == pivot, > pivot. This is Dijkstra's "Dutch national flag" problem. The equal block is already done and is never recursed into, so inputs with few distinct keys sort in near-linear time.

Complexity: best and average Θ(n log n), worst Θ(n²) (vanishingly unlikely with random pivots); O(log n) stack space with the smaller-side trick; in-place; not stable. When to use: in-memory arrays of primitives where stability is irrelevant; its tight inner loop and cache-friendly sequential access make it the fastest general sort in many languages' standard libraries.

Remember: quicksort does its work in partition; randomize the pivot, use three-way partitioning for duplicates, and recurse on the smaller side.

Heapsort

Intuition: a tournament. Arrange the items into a max-heap (M25), where every parent beats its children, so the champion sits at the root. Swap the champion to the end of the array, shrink the heap by one, and let the new root "sift down" to restore the heap. Repeat.

Invariant: a[0:end] is a max-heap and a[end:] holds the largest items in sorted order, each at least as large as everything in the heap. Complexity: Θ(n log n) worst case, O(1) extra space, in-place, not stable. Its random-looking memory access makes it slower than quicksort in practice, so it is used as a safety net (introsort) and when worst-case guarantees and O(1) memory are both required. With heapq you can also write [heappop(h) for _ in range(len(h))]; for top-k problems use heapq.nsmallest/nlargest.

The Ω(n log n) lower bound for comparison sorts

Merge sort, heapsort, and (on average) quicksort all take about n log n. Is that a coincidence, or could a cleverer comparison sort do better? It cannot, and the argument is beautiful.

Any algorithm that learns about the order only by comparing pairs (a[i] < a[j]?) can be drawn as a decision tree: each internal node is a comparison, each branch is its yes/no answer, and each leaf is a final ordering. Running the algorithm on an input is following one path from root to leaf.

• The tree must have at least n! leaves: every one of the n! orderings of distinct inputs needs its own leaf, or two different inputs would get the same rearrangement.
• A binary tree of height h has at most 2ʰ leaves, so 2ʰ ≥ n!, giving h ≥ log₂(n!).
• log₂(n!) ≥ log₂((n/2)^(n/2)) = (n/2) log₂(n/2) = Ω(n log n). (Stirling's formula sharpens this to n log₂ n − 1.44n.)

The height is the worst-case number of comparisons, so every comparison sort needs Ω(n log n) comparisons in the worst case. Merge sort and heapsort are asymptotically optimal.

Remember: sorting by comparisons alone needs at least log₂(n!) ≈ n log₂ n comparisons in the worst case. To beat it you must use more than comparisons, such as the digits of the keys.

Counting sort and radix sort

If keys are small integers, you do not need to compare them at all. Counting sort: intuition is a post office sorting letters into numbered pigeonholes. Count how many items have each key, turn the counts into starting positions (a prefix sum), then place each item directly into its slot.

count[k] = number of items with key k          for k in 0..K-1
start[k] = count[0] + ... + count[k-1]          (prefix sums)
for item in input (left to right):
    out[start[key(item)]] = item; start[key(item)] += 1

Placing items left to right makes it stable. Time Θ(n + K), space Θ(n + K), where K is the key range. Great when K is O(n) (ages, grades, bytes); useless when K is huge (64-bit IDs).

Radix sort extends this to big keys: sort by the least significant digit with a stable counting sort, then the next digit, and so on. Invariant: after pass d, the items are sorted by their last d digits; stability of each pass is what preserves the earlier digits' order. With d digits in base b, time is Θ(d · (n + b)). For 32-bit integers in base 256 that is 4 linear passes.

When to use: large arrays of fixed-width integers or strings (radix sort is the basis of fast GPU sorts and of sorting suffixes). In pure Python, sorted is usually still faster because it runs in C; numpy's np.sort(kind="stable") uses radix sort for 16-bit and smaller integer types.

Remember: non-comparison sorts escape the n log n bound by exploiting key structure; they need small integer keys or fixed-width digits.

Python's sort: Timsort, galloping, and Powersort

list.sort() sorts a list in place and returns None; sorted(iterable) builds a new list from any iterable. Both use the same algorithm, designed by Tim Peters in 2002 for CPython and later adopted by Java, Android, V8, and Swift. It is a hybrid of merge sort and insertion sort tuned for real-world data, which is rarely random: it often contains already-ordered stretches.

• Runs. It scans the list for natural runs: maximal stretches that are already ascending (or strictly descending, which it reverses in place). Short runs are extended to a minimum length (minrun, between 32 and 64) using binary insertion sort.
• Merging runs. Runs are pushed on a stack and merged with neighbors. Which neighbors to merge, and when, is the merge policy. Merging only adjacent runs is what keeps the sort stable.
• Galloping. When one run keeps "winning" during a merge (say, all of run A's next 7 items are smaller than run B's head), the merge switches to galloping mode: exponential search (1, 3, 7, 15, ... ahead) followed by binary search to find how far it can copy in one block. Merging a run of 10 into a run of a million then costs about log comparisons per item instead of linear.
• Powersort. In Python 3.11 CPython replaced Timsort's original merge-collapse rules with the Powersort merge policy of J. Ian Munro and Sebastian Wild. It assigns each boundary between runs a "power" based on where the run midpoints fall in a conceptual binary split of the array, and merges so the resulting merge tree is provably near-optimal (within a small constant of the entropy of the run lengths). Timsort's rules had an edge case where merge costs could be noticeably worse than necessary.

The upshot: Python's sort is O(n log n) worst case, O(n) on already sorted or reverse-sorted input, and close to O(n + n·H) on data made of a few runs (H is the entropy of the run lengths). It is stable and uses up to n/2 extra pointers.

Remember: in Python, call sorted or list.sort. Writing your own sort is for learning, for special key structures, or for data that does not fit in memory.

Key functions, multi-key sorts, and cmp_to_key

The key= argument maps each item to the value to compare. Python calls it exactly once per item (the decorate-sort-undecorate pattern done for you), so expensive keys are fine. reverse=True flips the order while staying stable.

The stability trick for mixed directions

You cannot negate a string. To sort by name descending and then by age ascending, sort in passes from the least significant key to the most significant, relying on stability:

functools.cmp_to_key

Sometimes the order is defined by comparing two items directly, not by a per-item key. Classic example: arrange numbers to form the largest concatenation. "9" should come before "34" because "934" > "349". Write a three-way comparison function (negative, zero, positive) and wrap it:

Remember: tuples sort lexicographically, so key=lambda r: (primary, secondary) is the idiomatic multi-key sort; negate numbers for descending, or use stable multi-pass sorts.

Benchmarking sorts with timeit

Big-O tells you the shape of the curve, not the constants. To know which is faster on your data, measure. timeit runs code many times and reports the total, avoiding one-off noise. Report the minimum of several repeats: the minimum is the run least disturbed by other processes.

Doubling n roughly quadruples insertion sort's time (O(n²)) and slightly more than doubles merge sort's (O(n log n)). sorted is the same shape as merge sort but 20 to 100 times faster because it runs in C.

Race mode

Use the visualizer's race mode to run two algorithms side by side on the same input and see the asymptotic difference with your own eyes: choose one algorithm, pick a rival in the race vs menu, and press Play. Race merge sort against insertion sort on the shuffled array first, then use the second visualizer, which starts from a nearly sorted array, where insertion sort suddenly wins.

Choosing a sort

Practice

def insertion_sort(a):
    for i in range(1, len(a)):
        item = a[i]
        j = i - 1
        while j >= 0 and a[j] > item:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = item

def merge_sort(items, key=lambda x: x):
    if len(items) <= 1:
        return list(items)
    mid = len(items) // 2
    left = merge_sort(items[:mid], key)
    right = merge_sort(items[mid:], key)
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if key(right[j]) < key(left[i]):
            out.append(right[j])
            j += 1
        else:
            out.append(left[i])
            i += 1
    out.extend(left[i:])
    out.extend(right[j:])
    return out

def partition3(a, pivot):
    lt, i, gt = 0, 0, len(a)
    while i < gt:
        if a[i] < pivot:
            a[lt], a[i] = a[i], a[lt]
            lt += 1
            i += 1
        elif a[i] > pivot:
            gt -= 1
            a[i], a[gt] = a[gt], a[i]
        else:
            i += 1
    return lt, gt

def radix_sort(nums):
    result = list(nums)
    if not result:
        return result
    place = 1
    largest = max(result)
    while place <= largest:
        buckets = [[] for _ in range(10)]
        for x in result:
            buckets[(x // place) % 10].append(x)
        result = [x for bucket in buckets for x in bucket]
        place *= 10
    return result

def leaderboard(players):
    ranked = sorted(players, key=lambda p: (-p["score"], p["time"], p["name"]))
    return [p["name"] for p in ranked]

from functools import cmp_to_key

def largest_number(nums):
    def compare(a, b):
        if a + b > b + a:
            return -1
        if a + b < b + a:
            return 1
        return 0

    digits = sorted(map(str, nums), key=cmp_to_key(compare))
    result = "".join(digits)
    return "0" if result.lstrip("0") == "" else result

Mini-project: external merge sort

pixi init extsort && cd extsort
pixi add pytest
pixi run python extsort.py big.txt sorted.txt --chunk-lines 10000

import heapq
import tempfile
from collections.abc import Iterator
from pathlib import Path

def make_runs(src: Path, chunk_lines: int, workdir: Path) -> list[Path]:
    """Split src into sorted run files of at most chunk_lines lines each."""
    ...

def read_lines(path: Path) -> Iterator[str]:
    with path.open(encoding="utf-8") as fh:
        yield from fh

def merge_runs(runs: list[Path], dest: Path) -> None:
    """k-way merge with heapq.merge, which holds only one line per run in memory."""
    with dest.open("w", encoding="utf-8") as out:
        out.writelines(heapq.merge(*(read_lines(r) for r in runs)))

Quiz

Recap

• Stable sorts keep ties in order; in-place sorts use O(1) or O(log n) extra memory.
• Bubble, selection, and insertion sort are O(n²); insertion sort is O(n + inversions) and great on nearly sorted data.
• Merge sort: Θ(n log n) always, stable, O(n) extra space. Quicksort: fast on average, O(n²) worst case; randomize and use three-way partitioning. Heapsort: Θ(n log n) worst case in O(1) space, not stable.
• Comparison sorts need Ω(n log n) comparisons (decision-tree argument); counting and radix sort avoid comparisons.
• Python's sort is a stable, adaptive merge sort with runs, galloping, and (since 3.11) the Powersort merge policy.
• Use key= with tuples for multi-key sorts, itemgetter/attrgetter for speed and clarity, and cmp_to_key only when you must compare pairs.

Going further

• Sorting Techniques HOWTO in the Python docs
• listsort.txt: Tim Peters' own description of the algorithm, updated for Powersort
• timeit and heapq documentation
• Next: M30 Searching & Array Techniques cashes in on sorted data.