3 — Sorting

Sorting puts a sequence into order by a key. It is the most studied problem in algorithms, partly because it is useful on its own and partly because so many other problems become easy once the data is sorted: duplicates become adjacent, binary search becomes possible (chapter 2), closest pairs become neighbors, and merging, grouping and ranking become single passes.

This chapter covers every standard sorting algorithm, the selection problem (finding the k-th smallest element without sorting everything), and the lower bound that limits comparison sorting. Each algorithm below was implemented in plain Python and tested against sorted() on thousands of random inputs, including empty lists, single elements, all-equal lists, already sorted and reversed lists, and, for the stable ones, records with equal keys whose original order had to be preserved.

Timings in this chapter were measured with Python 3.14 on one Mac. Exact numbers will differ elsewhere. Python-level implementations are 10 to 100 times slower than the C code behind sorted(), so the comparisons that matter are between the Python implementations, and between shapes of input for the same algorithm.

Vocabulary

Stability matters whenever records are sorted by one field after being sorted by another. Sorting employees by department after sorting them by name, with a stable sort, leaves each department’s employees in name order. That is how multi-key sorts are done in Python:

people.sort(key=lambda p: p.name)        # secondary key first
people.sort(key=lambda p: p.dept)        # then primary key; ties keep name order

The same result in one pass is people.sort(key=lambda p: (p.dept, p.name)).

The quadratic sorts

Bubble, insertion and selection sort each take $\Theta(n^2)$ time in the worst case. They are worth knowing because insertion sort is the fastest algorithm for small or nearly sorted inputs, and because each one introduces an idea that the faster algorithms reuse.

Bubble sort

Bubble sort sweeps through the array swapping adjacent elements that are out of order. After the first pass, the largest element has “bubbled” to the end; after the $k$-th pass, the last $k$ positions are final.

def bubble_sort(a):
    n = len(a)
    for end in range(n - 1, 0, -1):
        swapped = False
        for i in range(end):
            if a[i + 1] < a[i]:
                a[i], a[i + 1] = a[i + 1], a[i]
                swapped = True
        if not swapped:          # no swaps: already sorted
            break
    return a

pass 1:  5 1 4 2 8  ->  1 5 4 2 8  ->  1 4 5 2 8  ->  1 4 2 5 8  ->  1 4 2 5 8
pass 2:  1 4 2 5 | 8               ->  1 2 4 5 | 8
pass 3:  1 2 4 | 5 8   no swaps, stop

Each swap removes exactly one inversion, so the number of swaps equals the number of inversions: $n(n-1)/4$ on average. With the early exit, sorted input takes one pass, $\Theta(n)$. It is stable (only strictly greater elements are swapped) and in place.

Bubble sort has no practical use. In the measurements below it was the slowest algorithm on every input except sorted input, and 1.5 to 2.6 times slower than insertion sort, which does the same number of element moves with fewer comparisons and shifts instead of swaps.

Insertion sort

Insertion sort keeps a sorted prefix and inserts each new element into it, shifting larger elements one place right.

def insertion_sort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a)
    for i in range(lo + 1, hi):
        x = a[i]
        j = i - 1
        while j >= lo and x < a[j]:
            a[j + 1] = a[j]      # shift larger elements right
            j -= 1
        a[j + 1] = x
    return a

The invariant: before iteration $i$, a[lo:i] holds the original first elements in sorted order.

[5 | 2 4 6 1 3]    insert 2:  [2 5 | 4 6 1 3]
[2 5 | 4 6 1 3]    insert 4:  [2 4 5 | 6 1 3]
[2 4 5 | 6 1 3]    insert 6:  [2 4 5 6 | 1 3]
[2 4 5 6 | 1 3]    insert 1:  [1 2 4 5 6 | 3]
[1 2 4 5 6 | 3]    insert 3:  [1 2 3 4 5 6]

Each shift removes one inversion, so the running time is $\Theta(n + I)$ for $I$ inversions. That makes insertion sort:

• $\Theta(n)$ on sorted input and on any input with $O(n)$ inversions, such as a sorted list with a few late appends.
• $\Theta(n^2)$ on reversed input and on average.
• Stable (the < test stops at equal elements) and in place.
• Online: it can sort elements as they arrive.

Its inner loop is tight and touches adjacent memory, so for short arrays it beats every $O(n \log n)$ algorithm. Production sorts use it below a cutoff: Timsort for runs shorter than its minimum run length (up to 64 elements, with binary search to find the insertion point), introsort implementations for partitions below about 16 elements. Binary insertion sort finds the position with binary search, reducing comparisons to $O(n \log n)$ while the shifts stay $O(n^2)$; it helps when comparisons are expensive, as they are for Python objects.

Selection sort

Selection sort finds the minimum of the unsorted part and swaps it into the next position.

def selection_sort(a):
    n = len(a)
    for i in range(n - 1):
        m = i
        for j in range(i + 1, n):
            if a[j] < a[m]:
                m = j
        a[i], a[m] = a[m], a[i]
    return a

It always makes $n(n-1)/2$ comparisons, so it is $\Theta(n^2)$ on every input, sorted or not; the measurements show identical times for every shape. It makes at most $n - 1$ swaps, which is its one virtue: when writes are far more expensive than reads, it moves each element at most once. It is not stable, because the long-distance swap can jump an element past an equal one: sorting [2a, 2b, 1] swaps 2a with 1, giving [1, 2b, 2a].

Selection sort’s idea, “repeatedly extract the minimum”, becomes heap sort when the linear scan is replaced by a heap.

Merge sort

Merge sort is the canonical divide-and-conquer algorithm. Split the array in half, sort each half recursively, and merge the two sorted halves. John von Neumann described it in 1945.

The merge step is where the work happens. With two sorted lists, the smallest remaining element overall is the smaller of their two front elements, so a single pass with two pointers produces the merged result.

left:  [2 5 7]      right: [1 3 8 9]
        ^                   ^
compare 2,1 -> take 1   [1]
compare 2,3 -> take 2   [1 2]
compare 5,3 -> take 3   [1 2 3]
compare 5,8 -> take 5   [1 2 3 5]
compare 7,8 -> take 7   [1 2 3 5 7]
left empty  -> copy     [1 2 3 5 7 8 9]

def merge_sort(a):
    if len(a) <= 1:
        return a
    buf = a[:]
    def sort(lo, hi):                 # sorts a[lo:hi]
        if hi - lo <= 1:
            return
        mid = (lo + hi) // 2
        sort(lo, mid)
        sort(mid, hi)
        if not a[mid] < a[mid - 1]:   # halves already in order
            return
        buf[lo:hi] = a[lo:hi]
        i, j, k = lo, mid, lo
        while i < mid and j < hi:
            if buf[j] < buf[i]:       # strict: ties take from the left, so stable
                a[k] = buf[j]; j += 1
            else:
                a[k] = buf[i]; i += 1
            k += 1
        while i < mid:
            a[k] = buf[i]; i += 1; k += 1
        while j < hi:
            a[k] = buf[j]; j += 1; k += 1
    sort(0, len(a))
    return a

Three details matter:

• Stability comes from the strict comparison. When the two front elements are equal, the left one, which came first in the input, is taken first. Writing <= the other way round silently breaks stability.
• One buffer is allocated once and reused, instead of slicing new lists at every level, which would allocate $O(n \log n)$ memory in total.
• The “already in order” check skips the merge when the last element of the left half is not greater than the first of the right. It costs one comparison per merge and makes sorted input run in $\Theta(n)$.

Complexity

The recurrence is $T(n) = 2T(n/2) + \Theta(n)$, case 2 of the Master Theorem (chapter 1): $\Theta(n \log n)$ in the worst, average and best case (without the in-order check). The number of comparisons in the worst case is at most $n \lceil \log_2 n \rceil - 2^{\lceil \log_2 n \rceil} + 1$, within a few percent of the lower bound proved below. Extra space is $\Theta(n)$ for the buffer plus $\Theta(\log n)$ for the recursion.

Variants and uses

• Bottom-up merge sort skips recursion: merge pairs of size 1, then 2, then 4. Same complexity, no stack.
• Natural merge sort starts from the runs already present in the data. Timsort is the refined version.
• External sorting. When the data does not fit in memory, sort chunks that do, write them as runs, and merge the runs with a k-way merge using a heap (chapter 9). Merge sort reads and writes sequentially, which suits disks. PostgreSQL’s ORDER BY on a result larger than work_mem spills to disk and runs an external merge sort of this kind.
• Linked lists. Merge sort needs no random access, and merging linked lists needs no buffer, so it is the standard way to sort a linked list in $O(n \log n)$ (“Sort List”, chapter 6).
• Counting inversions. During the merge, whenever an element is taken from the right half, it is smaller than every remaining element of the left half, so it forms mid - i inversions with them. Adding these up counts all inversions in $O(n \log n)$. The same idea solves “Count of Smaller Numbers After Self” and “Reverse Pairs”.

Quicksort

Quicksort, developed by Tony Hoare in 1959 and published in 1961, also divides and conquers, but it does the work before recursing rather than after. Choose a pivot, partition the array so that everything smaller than the pivot is on its left and everything larger on its right, then sort the two sides recursively. No merge is needed: once both sides are sorted, the whole array is.

Quicksort is in place, has a tight inner loop with sequential memory access, and on average makes about $2n \ln n \approx 1.39 n \log_2 n$ comparisons. For decades it was the default general-purpose sort in C libraries and still underlies most unstable library sorts.

Lomuto partition

The Lomuto scheme, named after Nico Lomuto and popularized by Jon Bentley’s Programming Pearls, takes the last element as the pivot and scans left to right, keeping a boundary i such that a[lo:i] holds elements smaller than the pivot.

def lomuto_partition(a, lo, hi):
    """Partition a[lo..hi] around a[hi]. Returns the pivot's final index."""
    pivot = a[hi]
    i = lo
    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]
    return i

Invariant during the loop: a[lo:i] < pivot, a[i:j] >= pivot, a[j:hi] unexamined.

pivot = 4
 [3 7 1 6 2 4]   i=0
  ^ 3<4 swap a[0],a[0], i=1
 [3 7 1 6 2 4]   7>=4 skip
 [3 1 7 6 2 4]   1<4 swap a[1],a[2], i=2
 [3 1 7 6 2 4]   6>=4 skip
 [3 1 2 6 7 4]   2<4 swap a[2],a[4], i=3
 [3 1 2 4 7 6]   finally swap pivot into a[3]
         ^ pivot in final place, returns 3

The pivot ends in its final sorted position, and both recursive calls exclude it.

Hoare partition

Hoare’s original scheme runs two indices toward each other from the ends. The left index stops at an element that is not smaller than the pivot, the right index stops at one that is not larger, and the two are swapped.

def hoare_partition(a, lo, hi):
    """Partition a[lo..hi] around a[(lo+hi)//2]. Returns p with
    a[lo..p] <= pivot <= a[p+1..hi]."""
    pivot = a[(lo + hi) // 2]
    i, j = lo - 1, hi + 1
    while True:
        i += 1
        while a[i] < pivot:
            i += 1
        j -= 1
        while pivot < a[j]:
            j -= 1
        if i >= j:
            return j
        a[i], a[j] = a[j], a[i]

The return value is different from Lomuto’s, and confusing the two is a common bug. Hoare’s partition returns a split point p such that every element of a[lo..p] is at most the pivot and every element of a[p+1..hi] is at least the pivot. The pivot is not necessarily at p, so the recursive calls are on [lo, p] and [p+1, hi], including p. The pivot must not be the last element: with a[hi] as the pivot, the split can be p = hi and the recursion never shrinks. Choosing the middle element (or moving a random pivot there) avoids this.

The difference on equal keys is dramatic. Sorting arrays in which every element is the same value:

Lomuto quadruples with each doubling, which is quadratic. Hoare doubles and a bit, which is $n \log n$. Three-way partitioning, below, is linear on this input. On real data, “all equal” appears as “few distinct values”: sorting 100,000 values drawn from 10 distinct keys took 5,350 ms with Lomuto against 73 ms with Hoare.

Three-way partitioning

Dijkstra’s Dutch national flag partition splits the range into three parts: less than, equal to, and greater than the pivot. Elements equal to the pivot are finished and never touched again.

def quicksort_3way(a):
    """Dijkstra's three-way partition: < pivot | == pivot | > pivot."""
    def sort(lo, hi):
        while lo < hi:
            pivot = a[random.randint(lo, hi)]
            lt, i, gt = lo, lo, hi
            while i <= gt:
                if a[i] < pivot:
                    a[lt], a[i] = a[i], a[lt]; lt += 1; i += 1
                elif pivot < a[i]:
                    a[i], a[gt] = a[gt], a[i]; gt -= 1
                else:
                    i += 1
            if lt - lo < hi - gt:
                sort(lo, lt - 1); lo = gt + 1
            else:
                sort(gt + 1, hi); hi = lt - 1
    sort(0, len(a) - 1)
    return a

Invariant: a[lo:lt] < pivot, a[lt:i] == pivot, a[i:gt+1] unexamined, a[gt+1:hi+1] > pivot. With $k$ distinct keys the running time is $O(n \log k)$, linear when $k$ is constant. On distinct keys it does a little more work per element than Hoare’s scheme. The same partition solves “Sort Colors” (an array of 0s, 1s and 2s) in one pass.

Pivot choice and the worst case

Quicksort’s running time depends on how evenly the pivot splits the range.

Any constant-proportion split gives $n \log n$ (by Akra–Bazzi, chapter 1). The quadratic case happens when the pivot is repeatedly the smallest or largest element. With the first or last element as pivot, that is exactly what happens on sorted and reversed input, which are among the most common inputs in practice. The remedies:

• Random pivot. Expected $O(n \log n)$ comparisons on every input; the quadratic case requires a sequence of unlucky draws whose probability vanishes as $n$ grows. The implementations here use it.
• Median of three. Use the median of the first, middle and last elements. It fixes sorted and reversed input and gives a better expected split on random data, but specific “median-of-3 killer” sequences still force quadratic time, and an attacker who knows the scheme can construct them.
• Ninther. The median of three medians of three, used for large arrays.

The recursion depth is a separate problem. Recursing on both sides naively can reach depth $n$ on a bad sequence, overflowing the stack. All the implementations here recurse on the smaller side and loop on the larger, which bounds the depth at $\log_2 n$ whatever the pivots:

def quicksort_hoare(a):
    def sort(lo, hi):
        while lo < hi:
            r = random.randint(lo, hi)
            m = (lo + hi) // 2
            a[r], a[m] = a[m], a[r]            # random pivot moved to the middle
            p = hoare_partition(a, lo, hi)
            if p - lo < hi - p:
                sort(lo, p); lo = p + 1
            else:
                sort(p + 1, hi); hi = p
    sort(0, len(a) - 1)
    return a

Quicksort is not stable: partitioning swaps elements across long distances.

Introsort

Introsort, introduced by David Musser in 1997, makes quicksort’s worst case $O(n \log n)$ without giving up its average speed. It runs quicksort, counts the recursion depth, and if the depth exceeds about $2 \log_2 n$, which signals a run of bad pivots, it switches to heap sort for that subarray. Ranges below a small cutoff are finished with insertion sort.

def introsort(a):
    """Quicksort (median of three, Hoare) with a heap sort fallback when the
    recursion gets too deep, and insertion sort for small ranges."""
    def sort(lo, hi, depth):
        while hi - lo > 16:
            if depth == 0:
                heap_sort_range(a, lo, hi + 1)
                return
            depth -= 1
            m = median_of_three(a, lo, hi)
            p = hoare_partition(a, lo, hi)
            if p - lo < hi - p:
                sort(lo, p, depth); lo = p + 1
            else:
                sort(p + 1, hi, depth); hi = p
        insertion_sort(a, lo, hi + 1)
    if len(a) > 1:
        sort(0, len(a) - 1, 2 * int(math.log2(len(a))))
    return a

median_of_three orders a[lo], a[mid] and a[hi] so that the median lands at mid, where hoare_partition picks it up as the pivot. Introsort was the fastest Python implementation on random input at both sizes measured, and close to the fastest on every other shape. C++ standard library implementations of std::sort are typically introsort, because the standard requires $O(n \log n)$ comparisons. Pattern-defeating quicksort (pdqsort), by Orson Peters, extends the idea with detection of sorted patterns and better handling of equal keys; Go’s standard library switched to it in Go 1.19.

Dual-pivot quicksort partitions around two pivots into three ranges. Vladimir Yaroslavskiy’s version has been Java’s sort for primitive arrays since Java 7. Its advantage on modern hardware comes mainly from fewer memory scans rather than fewer comparisons.

Heap sort

Heap sort, published by J. W. J. Williams in 1964, is selection sort with a better data structure. A binary max-heap stored in the array itself (children of index $i$ at $2i + 1$ and $2i + 2$, every parent at least as large as its children; see chapter 9) gives the maximum in O(1) and restores the heap property in $O(\log n)$ after removing it.

1. Heapify the array bottom-up: sift down every internal node from the last one to the root. Robert Floyd showed this takes $O(n)$, not $O(n \log n)$, because most nodes are near the bottom and sift only a short distance.
2. Repeat $n - 1$ times: swap the root (the maximum) with the last element of the heap, shrink the heap by one, and sift the new root down.

def sift_down(a, start, i, end):
    """Max-heap stored in a[start:end], node i relative to start."""
    while True:
        child = 2 * i + 1
        if child >= end - start:
            return
        c = start + child
        if child + 1 < end - start and a[c] < a[c + 1]:
            c += 1; child += 1
        if not a[start + i] < a[c]:
            return
        a[start + i], a[c] = a[c], a[start + i]
        i = child

def heap_sort_range(a, lo, hi):
    n = hi - lo
    for i in range(n // 2 - 1, -1, -1):        # heapify bottom-up: O(n)
        sift_down(a, lo, i, hi)
    for end in range(hi - 1, lo, -1):
        a[lo], a[end] = a[end], a[lo]          # move max to its final place
        sift_down(a, lo, 0, end)

heapify [4 10 3 5 1]  ->  [10 5 3 4 1]
           10
          /  \
         5    3
        / \
       4   1
swap root with last, sift: [5 4 3 1 | 10]
swap root with last, sift: [4 1 3 | 5 10]
swap root with last, sift: [3 1 | 4 5 10]
swap root with last:       [1 | 3 4 5 10]

Heap sort is $O(n \log n)$ in the worst case, in place with O(1) extra memory, and not stable. Its weakness is speed: it makes about $2n \log_2 n$ comparisons (measured below at 1.99 times the lower bound, against 1.06 for merge sort), and sift-down jumps between index $i$ and $2i$, which defeats the cache for large arrays. It was the slowest $O(n \log n)$ sort in the measurements. Its role is as a guarantee: introsort’s fallback, and the right choice when memory is fixed and a worst-case bound is required.

When only the $k$ smallest elements are needed, a heap avoids sorting everything: heapq.nsmallest(k, a) runs in $O(n \log k)$.

Selection: the k-th smallest element

The selection problem asks for the element that would be at index $k$ if the array were sorted: the minimum for $k = 0$, the median for $k = \lfloor (n-1)/2 \rfloor$. Sorting solves it in $O(n \log n)$. It can be solved in $O(n)$.

Quickselect

Quickselect, also by Hoare (1961), partitions like quicksort but recurses into only the side that contains index $k$.

def quickselect(a, k):
    """k-th smallest (0-based). Rearranges a. Expected O(n)."""
    lo, hi = 0, len(a) - 1
    while True:
        if lo == hi:
            return a[lo]
        r = random.randint(lo, hi)
        a[r], a[hi] = a[hi], a[r]
        p = lomuto_partition(a, lo, hi)
        if k == p:
            return a[p]
        if k < p:
            hi = p - 1
        else:
            lo = p + 1

With good pivots, the work is $n + n/2 + n/4 + \dots < 2n$. With random pivots the expected number of comparisons is at most about $3.4n$, so the expected time is $O(n)$. The worst case is $\Theta(n^2)$, for the same reason as quicksort. After it returns, the array is partitioned around position $k$: everything before is at most a[k] and everything after is at least it, which directly answers “the k smallest elements” in any order. This is C++‘s std::nth_element.

The version above uses a Lomuto partition, so it inherits Lomuto’s quadratic behavior on many equal keys; a three-way partition fixes that.

Classic uses: “Kth Largest Element in an Array” (select index $n - k$), “K Closest Points to Origin” (select by distance), “Top K Frequent Elements” (select over counts), and the median in statistics.

Median of medians

Can selection be linear in the worst case? Blum, Floyd, Pratt, Rivest and Tarjan showed in 1973 that it can, by choosing a pivot that is guaranteed to be near the middle.

1. Split the $n$ elements into groups of 5, and find the median of each group (constant work per group).
2. Recursively select the median of those $n/5$ medians. Use it as the pivot.
3. Partition around the pivot and recurse into the side containing index $k$.

def median_of_medians_select(a, k):
    """k-th smallest (0-based) in worst-case O(n). Does not modify a."""
    while True:
        if len(a) <= 5:
            return sorted(a)[k]
        medians = [sorted(a[i:i + 5])[len(a[i:i + 5]) // 2]
                   for i in range(0, len(a), 5)]
        pivot = median_of_medians_select(medians, len(medians) // 2)
        lows = [x for x in a if x < pivot]
        highs = [x for x in a if pivot < x]
        n_eq = len(a) - len(lows) - len(highs)
        if k < len(lows):
            a = lows
        elif k < len(lows) + n_eq:
            return pivot
        else:
            k -= len(lows) + n_eq
            a = highs

Why it is linear. Arrange the groups as columns, each sorted, with the columns ordered by their medians:

each column is a group of 5, sorted small (top) to large (bottom);
columns are ordered left to right by their medians (middle row)

   a  a  a  .  .  .  .
   a  a  a  .  .  .  .
   a  a  M  b  b  b  b      M = median of medians
   .  .  b  b  b  b  b
   .  .  b  b  b  b  b

a: at most M   (at or above a median that is at most M)
b: at least M  (at or below a median that is at least M)

Half of the $n/5$ group medians are at most the pivot $M$, and each of those medians has two more elements in its group below it. So at least $3 \cdot n/10$ elements are at most $M$, and by symmetry at least $3n/10$ are at least $M$. Either side of the partition therefore has at most about $7n/10$ elements. The running time satisfies

$T(n) \le T(n/5) + T(7n/10) + O(n)$

The recursive calls together handle $n/5 + 7n/10 = 9n/10$ of the input, a fraction below 1, so the work shrinks geometrically: $cn(1 + 0.9 + 0.81 + \dots) = 10cn$. $T(n) = \Theta(n)$. Chapter 1 derives the same result with Akra–Bazzi.

Groups of 5 are the smallest odd size that works. With groups of 3, the guarantee is only $n/3$ on each side, the recurrence becomes $T(n/3) + T(2n/3) + O(n)$, the fractions sum to exactly 1, and the result is $\Theta(n \log n)$. Groups of 7 also give linear time.

The constant factor is large. Finding the median of random floats:

Quickselect in Python matched sorted() in C at 100,000 elements and beat it by 2 times at a million, because linear beats $n \log n$ eventually even with a 10 to 50 times worse constant. Median of medians was about 4 times slower than quickselect. Its real use is as a fallback: introselect runs quickselect and switches to median of medians if progress stalls, getting quickselect’s speed with a linear worst case. A heap is the wrong tool when $k$ is near $n/2$; it shines for small $k$.

Linear-time sorts

The $n \log n$ lower bound below applies only to algorithms that learn the order by comparing keys. When keys are small integers, or can be broken into digits, sorting can index by the key instead, and run in linear time.

Counting sort

For integer keys in a range $[0, k)$: count how many times each key occurs, convert the counts into starting positions with a prefix sum, and place each element at its key’s next position.

def counting_sort(a, key=lambda x: x, k=None):
    """Stable sort of items whose key is an int in [0, k)."""
    if not a:
        return a
    if k is None:
        k = max(key(x) for x in a) + 1
    count = [0] * k
    for x in a:
        count[key(x)] += 1
    pos = 0
    for v in range(k):                         # prefix sums: start of each key
        count[v], pos = pos, pos + count[v]
    out = [None] * len(a)
    for x in a:                                # left to right keeps it stable
        out[count[key(x)]] = x
        count[key(x)] += 1
    return out

input keys:   2 0 2 1 0 2
counts:       key 0: 2   key 1: 1   key 2: 3
starts:       key 0 at 0, key 1 at 2, key 2 at 3
placement:    out = [0 0 1 2 2 2], equal keys in input order

Time and space are $\Theta(n + k)$. It is stable because elements are placed in input order, and that stability is what makes radix sort work. It is useful only when $k$ is $O(n)$ or smaller: sorting a thousand 32-bit integers with counting sort would need a 4-billion-entry count array. In the measurements, counting sort was run only on the “few unique” input, where $k = 10$.

If only the keys matter (no attached records), the placement pass can be replaced by writing each key count[v] times.

Radix sort

Radix sort handles large integer keys by sorting on one digit at a time. Least-significant-digit (LSD) radix sort runs a stable counting sort on the lowest digit, then the next, up to the highest. After pass $i$, the array is sorted by the lowest $i$ digits, because each pass is stable: elements with equal digit $i$ stay in the order established by the lower digits.

def radix_sort(a, base=256):
    """LSD radix sort for non-negative ints, one stable counting pass per digit."""
    if not a:
        return a
    m, shift = max(a), 0
    while (m >> shift) > 0 or shift == 0:
        a = counting_sort(a, key=lambda x: (x >> shift) & (base - 1), k=base)
        shift += base.bit_length() - 1
    return a

base 10 for readability
input:          170  45  75  90  802  24   2  66
by ones:        170  90 802   2   24  45  75  66
by tens:        802   2  24  45  66 170  75  90
by hundreds:      2  24  45  66  75  90 170 802

With $d$ digits in base $b$, time is $\Theta(d(n + b))$ and extra space $\Theta(n + b)$. For $w$-bit integers in base $2^r$, $d = w/r$; choosing $r \approx \log_2 n$ gives $\Theta(wn/\log n)$. Base 256 here means 4 passes for 30-bit keys.

Most-significant-digit (MSD) radix sort works from the top digit down, recursing into each bucket. It suits variable-length keys such as strings, can stop early when a bucket has one element, and is the basis of fast string sorting.

Negative integers need an offset or a separate pass for the sign. Floats can be radix-sorted by reinterpreting their IEEE 754 bits with the sign handled specially.

Bucket sort

Bucket sort assumes keys are spread roughly uniformly over a known range. It creates $n$ buckets over the range, drops each element into its bucket, sorts each bucket (usually with insertion sort), and concatenates.

def bucket_sort(a):
    """For floats in [0, 1): n buckets, each sorted with insertion sort."""
    n = len(a)
    buckets = [[] for _ in range(n)]
    for x in a:
        buckets[int(x * n)].append(x)
    out = []
    for b in buckets:
        out.extend(insertion_sort(b))
    return out

With uniform keys each bucket holds O(1) elements on average, and the expected time is $\Theta(n)$. With skewed keys most elements fall into a few buckets and insertion sort makes it quadratic:

The uniform column doubles with $n$; the skewed column more than triples. It is the same failure as interpolation search in chapter 2: any algorithm that predicts position from value is only as good as its assumption about the distribution. Choosing bucket boundaries from a sample of the data (as in sample sort) fixes it. Bucket sort is stable if each bucket is sorted stably.

Shell sort

Shell sort, published by Donald Shell in 1959, is insertion sort generalized to move elements long distances early. It runs insertion sort on elements a gap $h$ apart, for a decreasing sequence of gaps ending in 1. The final pass is ordinary insertion sort, but by then the array has few inversions and it runs fast.

def shell_sort(a):
    gaps = [701, 301, 132, 57, 23, 10, 4, 1]       # Ciura's sequence
    while gaps[0] < len(a) // 2:                    # extend by about x2.25
        gaps.insert(0, int(gaps[0] * 2.25))
    for gap in gaps:
        for i in range(gap, len(a)):
            x = a[i]
            j = i
            while j >= gap and x < a[j - gap]:
                a[j] = a[j - gap]
                j -= gap
            a[j] = x
    return a

The complexity depends on the gap sequence, and for many sequences it is still an open problem:

Shell sort is in place, not stable, uses no recursion, and has a small code footprint, which keeps it in use in embedded systems and some small C libraries. In the measurements it was competitive with merge sort and quicksort at 2,000 elements and only somewhat slower at 100,000.

Cycle sort

Every permutation decomposes into cycles: element at position 0 belongs at position 3, the element at 3 belongs at 7, the one at 7 belongs at 0. Cycle sort follows each cycle, writing each element directly into its final position. It finds an element’s final position by counting how many elements are smaller.

def cycle_sort(a):
    """In-place, minimizes writes. Returns number of writes."""
    writes = 0
    n = len(a)
    for start in range(n - 1):
        item = a[start]
        pos = start + sum(1 for i in range(start + 1, n) if a[i] < item)
        if pos == start:
            continue
        while item == a[pos]:                  # skip past duplicates
            pos += 1
        a[pos], item = item, a[pos]
        writes += 1
        while pos != start:                    # rotate the rest of the cycle
            pos = start + sum(1 for i in range(start + 1, n) if a[i] < item)
            while item == a[pos]:
                pos += 1
            a[pos], item = item, a[pos]
            writes += 1
    return writes

Counting smaller elements is $O(n)$ per element, so the time is $\Theta(n^2)$ always. What cycle sort minimizes is writes: each element is written at most once, and elements already in place are never written. Array writes needed to sort a random permutation of 1,000 elements:

All 1,000 elements were out of place, so 1,000 writes is the minimum possible. This matters for memory with limited write endurance, such as flash or EEPROM, and is otherwise a curiosity. Cycle sort is not stable.

The cyclic sort interview pattern

When the values are known to be the integers $1..n$ (or $0..n-1$), the final position of value $v$ is simply index $v - 1$, no counting needed. Repeatedly swapping each element into its home position sorts the array in $O(n)$:

def cyclic_sort(nums):
    """nums holds values 1..n (a permutation): place value v at index v-1."""
    i = 0
    while i < len(nums):
        j = nums[i] - 1
        if nums[i] != nums[j]:
            nums[i], nums[j] = nums[j], nums[i]
        else:
            i += 1
    return nums

Every swap puts at least one value into its home, where it stays, so there are at most $n$ swaps plus $n$ increments: $O(n)$ time, O(1) extra space. The nums[i] != nums[j] test, rather than i != j, is what keeps duplicates from causing an infinite swap loop.

The pattern’s power is with values in the range $1..n$ that are not a permutation. After the placement loop, every value that is present sits at its home, and any index $i$ whose value is not $i + 1$ reveals a missing number $i + 1$ and a duplicate value nums[i]. That solves a family of problems in $O(n)$ time without a hash set:

def find_disappeared(nums):
    """Find All Numbers Disappeared in an Array: values in 1..n, some repeated."""
    i = 0
    while i < len(nums):
        j = nums[i] - 1
        if nums[i] != nums[j]:
            nums[i], nums[j] = nums[j], nums[i]
        else:
            i += 1
    return [i + 1 for i, v in enumerate(nums) if v != i + 1]

input        [4 3 2 7 8 2 3 1]
after loop   [1 2 3 4 3 2 7 8]
              index 4 holds 3, index 5 holds 2: missing 5 and 6

def first_missing_positive(nums):
    """First Missing Positive: any ints; answer is in 1..n+1."""
    n = len(nums)
    i = 0
    while i < n:
        v = nums[i]
        if 1 <= v <= n and nums[v - 1] != v:
            nums[i], nums[v - 1] = nums[v - 1], v
        else:
            i += 1
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

The answer to First Missing Positive must lie in $1..n+1$, because $n$ slots can hold at most the values $1..n$. That observation is what lets values outside the range be ignored, and turns a problem that looks like it needs sorting or a hash set into an $O(n)$ time, $O(1)$ space pass. These functions modify their input; copy it first if the caller needs the original.

Timsort and Powersort

Python’s list.sort() and sorted() use Timsort, written by Tim Peters for Python 2.3 in 2002. Java uses it for sorting objects (since Java 7), and so do Android, V8 (JavaScript’s Array.prototype.sort) and Swift. It is a stable, adaptive merge sort designed around one observation: real data is rarely random. It often contains sorted or reversed stretches (timestamps, appended records, data that was sorted and then lightly edited), and an algorithm that exploits them can be much faster than $n \log n$.

Runs

Timsort scans the array once, left to right, identifying natural runs: maximal non-descending stretches, or strictly descending stretches, which it reverses in place. (Strictly descending, so that reversing never reorders equal elements and stability is preserved.)

A run shorter than minrun is extended to minrun elements with binary insertion sort. Minrun is chosen from $n$ so that $n / \text{minrun}$ is a power of two or slightly less, which keeps the merges balanced; for $n$ of 64 or more it falls between 32 and 64, and arrays shorter than 64 are sorted entirely with binary insertion sort. On random data almost every run is a minrun-sized chunk made by insertion sort; on structured data runs can be thousands of elements long and need no work at all.

Merge policy

Runs are pushed on a stack and merged with neighbors. Only adjacent runs may be merged, or stability would break. The order of merges determines the total cost: merging a long run with a very short one repeatedly is wasteful, the same way building a string by repeated concatenation is.

The original Timsort maintained invariants on the lengths of the top three runs on the stack, loosely based on the Fibonacci sequence. In 2015, researchers attempting to formally verify the Java implementation with the KeY verification system found that the invariants were not always maintained, and that crafted inputs could overflow the fixed-size run stack. Python corrected the invariant check; Java enlarged the run stack.

Since Python 3.11, CPython has used the merge policy of Powersort, from J. Ian Munro and Sebastian Wild’s 2018 paper “Nearly-Optimal Mergesorts”. For each pair of adjacent runs it computes a “power”: the depth at which the boundary between the two runs would sit in a perfectly balanced binary merge tree over the whole array, computed from the runs’ midpoints as fractions of $n$. Runs on the stack are merged while their power exceeds the newly computed one. The resulting merge cost is provably within a small additive term of optimal for the given run lengths, and the bookkeeping is simpler than the old invariants. The design notes in CPython’s Objects/listsort.txt describe it in detail. (CPython’s development branch has since also refined how minrun is chosen; Python 3.14 uses the scheme described above.)

Merging and galloping

Timsort merges two adjacent runs using temporary memory equal to the shorter run, which it copies out; it then merges from the side that lets it write into the vacated space. Before merging it trims each run: elements at the start of the first run that are already smaller than the second run’s first element are in place and skipped, and likewise at the end of the second run.

During a merge, it counts how many times in a row the winner came from the same run. Once that count reaches MIN_GALLOP (initially 7), it switches to galloping mode: instead of comparing one pair at a time, it searches the other run for where the current element belongs using exponential search (offsets 0, 1, 3, 7, 15, …, then binary search; chapter 2), and copies the whole block in one move. When galloping stops paying off it returns to one-at-a-time merging, and it adapts the threshold up or down depending on how well galloping has been working. On data where the runs interleave in large blocks, a merge of runs of lengths $m \le n$ costs about $O(m \log(n/m))$ comparisons instead of $O(m + n)$.

Complexity and behavior

The comparison count is very close to optimal. On a random permutation of 100,000 elements, sorted() made 1,531,798 comparisons against a theoretical minimum of 1,516,705, 1% above the lower bound.

Why Python uses Timsort rather than quicksort: Python’s sort must be stable (the language guarantees it), and in Python comparisons are expensive, because comparing two objects is a method call through the interpreter. Moving a pointer is cheap. So the algorithm that minimizes comparisons wins even if it moves more data, and Timsort makes far fewer comparisons than quicksort, heap sort or Shell sort.

A simplified version

The essential ideas fit in a short function: find runs, extend them to minrun with insertion sort, and merge neighbors. This version merges pairwise in rounds instead of using a run stack, and has no galloping:

def tim_lite(a, minrun=32):
    """Find natural runs, extend short ones to minrun with insertion sort,
    then merge neighbouring runs pairwise. No galloping, no run stack."""
    n = len(a)
    runs = []
    i = 0
    while i < n:
        j = i + 1
        if j < n and a[j] < a[i]:                      # strictly descending run
            while j < n and a[j] < a[j - 1]:
                j += 1
            a[i:j] = a[i:j][::-1]
        else:
            while j < n and not a[j] < a[j - 1]:
                j += 1
        end = min(max(j, i + minrun), n)
        insertion_sort(a, i, end)
        runs.append((i, end))
        i = end
    while len(runs) > 1:
        merged = []
        for r in range(0, len(runs) - 1, 2):
            (lo, mid), (_, hi) = runs[r], runs[r + 1]
            if a[mid] < a[mid - 1]:
                left = a[lo:mid]
                x, y, k = 0, mid, lo
                while x < len(left) and y < hi:
                    if a[y] < left[x]:
                        a[k] = a[y]; y += 1
                    else:
                        a[k] = left[x]; x += 1
                    k += 1
                a[k:k + len(left) - x] = left[x:]
            merged.append((lo, hi))
        if len(runs) % 2:
            merged.append(runs[-1])
        runs = merged
    return a

Even this simplified version is adaptive: in the measurements it sorted 100,000 sorted elements in 6 ms and reversed ones in 14 ms, against 92 ms for random input.

Measured comparison

Each cell is the best of three runs on a fresh copy of the same input. “Random” is integers drawn from $[0, 10^9)$; “few unique” is integers from $[0, 10)$. Counting sort was run only where the key range was small.

2,000 elements, milliseconds:

100,000 elements, milliseconds (quadratic sorts omitted):

What the tables show:

• Growth rates dominate. At 2,000 elements on random input the quadratic sorts are already 10 to 90 times slower than the $n \log n$ ones.
• Adaptivity is visible. Bubble, insertion, merge (with its in-order check), tim_lite and sorted() are dramatically faster on sorted input; sorted() handles a sorted 100,000-element list in 0.42 ms, about 20 times faster than a random one. Selection sort and heap sort take the same time whatever the input.
• Equal keys separate the quicksorts. Lomuto went quadratic on few unique values (5.35 s); three-way partitioning was 5 to 8 times faster than on random data.
• Introsort was the fastest Python comparison sort on random input, from median-of-three pivots, Hoare partitioning, and insertion sort for small ranges. On sorted input the run-detecting sorts beat it, and on few unique values three-way quicksort and counting sort did.
• Heap sort was the slowest $O(n \log n)$ sort, as predicted by its comparison count and memory access pattern.
• Radix sort’s cost is independent of order and depends only on the number of digit passes: 4 passes for 30-bit keys, 1 pass for keys below 10.
• sorted() beat every Python implementation, by a factor of 2 against counting sort on few unique keys and usually by a factor of 10 or more. It is written in C, it makes close to the minimum number of comparisons, and for lists of a single type such as all ints or all floats, CPython (since 3.7) pre-checks the types and uses a specialized comparison that avoids the generic object comparison machinery. In Python, implementing a sort by hand is for learning or for problems that need a modified algorithm (counting inversions, partial sorting, custom merge logic), never for speed.

The comparison-sort lower bound

Merge sort, heap sort and Timsort run in $O(n \log n)$. No comparison sort can do better in the worst case. The argument uses a decision tree.

Any comparison sort, run on inputs of size $n$, can be drawn as a binary tree. Each internal node is a comparison “is $a_i < a_j$?”, its two children are what the algorithm does next for each answer, and each leaf is a final answer: the permutation that sorts the input. Running the algorithm on a specific input traces one path from root to leaf, and the number of comparisons is the path’s length.

                    a1 < a2 ?
                 yes /      \ no
           a2 < a3 ?          a1 < a3 ?
          yes/   \no         yes/    \no
     [1,2,3]   a1 < a3 ?   [2,1,3]   a2 < a3 ?
              yes/   \no            yes/   \no
          [1,3,2]  [3,1,2]      [2,3,1]  [3,2,1]

the decision tree of insertion sort on 3 elements: 6 leaves, height 3

The argument:

1. There are $n!$ possible orderings of $n$ distinct keys, and each one needs a different leaf, because sorting two different orderings requires different rearrangements. So the tree has at least $n!$ leaves.
2. A binary tree of height $h$ has at most $2^h$ leaves.
3. So $2^h \ge n!$, and $h \ge \log_2 n!$.

The height is the worst-case number of comparisons. By Stirling’s approximation,

$\log_2 n! = n \log_2 n - n \log_2 e + O(\log n) \approx n \log_2 n - 1.443 n$

so every comparison sort makes $\Omega(n \log n)$ comparisons in the worst case. A stronger form holds too: the average depth of the leaves of a binary tree with $N$ leaves is at least $\log_2 N$, so the average over all input orderings is also $\Omega(n \log n)$. Randomization does not help either.

Measured against the exact bound $\lceil \log_2 n! \rceil$:

Python’s sort is within about 1% of the information-theoretic minimum.

What the bound does not cover:

• Non-comparison sorts (counting, radix, bucket) look at the keys’ values directly, so the decision tree argument does not apply to them. They pay instead with assumptions about the keys.
• Adaptive sorts on structured input. With few inversions or few runs, there are far fewer than $n!$ possible inputs, and the corresponding bound is lower. Timsort’s $O(n + n\mathcal{H})$ matches it.
• Few distinct keys. With $k$ distinct values, the number of distinguishable outcomes is a multinomial coefficient, and $O(n \log k)$ is achievable, as three-way quicksort does.

The same technique proves other lower bounds: searching a sorted array needs $\log_2(n + 1)$ comparisons, and deciding whether $n$ elements are all distinct needs $\Omega(n \log n)$ comparisons in the comparison model.

Choosing a sort

Summary

All time entries are $\Theta$ bounds on running time; for Shell sort the bounds depend on the gap sequence and are open for Ciura’s. Comparison sorts cannot beat $\Omega(n \log n)$ comparisons in the worst or average case; counting, radix and bucket sort escape the bound by using the keys’ values.