Lower bound and linear-time sorts

Why it exists

Merge sort and heap sort take $\Theta(n \log n)$. Can any algorithm do better? The answer has two halves, and both are exam material. No, if the only thing the algorithm may do with the keys is compare two of them: $\Omega(n \log n)$ comparisons are unavoidable. Yes, if the keys are small integers (or digits, or uniformly spread numbers): then counting sort, radix sort and bucket sort run in linear time, by looking inside the keys instead of comparing them.

Prerequisites

You need the comparison sorts (merge sort, quicksort) and the idea of stability (stability and comparison of sorts).

Precise definitions

Comparison sort model. The algorithm learns about the keys only through questions "is $a_i < a_j$?" with a yes/no answer. Every comparison sort in the syllabus (bubble, selection, insertion, merge, quick, heap) is of this kind.

Decision tree. For a fixed $n$, the behaviour of a comparison sort can be drawn as a binary tree: each internal node is a comparison of two positions, its two children correspond to the two answers, and each leaf is a final answer, namely a permutation that sorts the input. The number of comparisons on an input is the depth of the leaf reached; the worst case is the height of the tree.

Counting sort. For integer keys in $0, \ldots, k$: count how often each key occurs, turn the counts into end positions by prefix sums, and place the keys into the output by scanning the input from the last key to the first.

Radix sort (LSD). For keys of $d$ digits in base $b$: for the digit positions from the least significant to the most significant, sort the whole array by that digit with a stable sort (counting sort).

Bucket sort. For keys spread uniformly over $[0, 1)$: distribute the $n$ keys into $n$ buckets (key $x$ to bucket $\lfloor n x \rfloor$), sort each bucket (insertion sort), and concatenate.

How it works

The lower bound

Claim. Every comparison sort needs at least $\lceil \log_2 n! \rceil = \Omega(n \log n)$ comparisons in the worst case.

Proof. If the $n$ keys are distinct there are $n!$ possible orders, and a correct algorithm must reach a different leaf for each (two different orders need different permutations as output). So the decision tree has at least $n!$ leaves. A binary tree of height $h$ has at most $2^h$ leaves, so $2^h \ge n!$, i.e. $h \ge \log_2 n!$. By Stirling's approximation $n! > (n/e)^n$, hence $h \;\ge\; \log_2 n! \;>\; n \log_2 n - n \log_2 e \;=\; \Omega(n \log n).$ The same argument applies to the average number of comparisons: the average depth of $n!$ leaves of a binary tree is at least $\log_2 n!$. So no comparison sort has $o(n \log n)$ average or worst case. $\blacksquare$

Consequences: merge sort and heap sort are asymptotically optimal comparison sorts; quicksort is optimal on average. The table shows how the bound compares with two real algorithms for small $n$.

For $n \le 5$ the bound is exactly attained: an exhaustive search over all strategies gives the minimum worst-case numbers of comparisons $0, 1, 3, 5, 7$, which equal $\lceil \log_2 n! \rceil$. (Only the order $n \log n$ matters for the syllabus; whether the bound is attained exactly for every $n$ is not needed.) The same method gives other lower bounds, for example that finding the maximum of $n$ keys needs $n - 1$ comparisons: every key except the maximum must lose at least one comparison.

What the bound does not cover. An algorithm that uses the values of the keys (as an array index, as a digit) is not a comparison sort. The bound says nothing about it.

Counting sort

The animation shows the three passes on keys between $0$ and $4$: count each key, add up the counts so that $\text{count}[v]$ becomes the position just after the last key $v$, then place the keys backwards. The code is a real run.

Cost. The three loops run $n$, $k$ and $n$ times: $\Theta(n + k)$ time, and $\Theta(n + k)$ extra space (the count array of $k + 1$ cells and the output array). It is linear when $k = O(n)$, but if $k$ is much larger than $n$ (for example $k = n^2$) it is worse than a comparison sort. It makes no comparison between keys. It is stable: scanning backwards puts the last of several equal keys last, and equal keys end up in input order.

Radix sort

Sorting by the least significant digit first and then by each more significant digit works because each pass is stable: after the pass for digit $j$ the numbers are ordered by their last $j$ digits, since a stable sort by digit $j$ keeps the order by the lower digits among numbers with equal digit $j$. The program sorts eight 3-digit numbers with one counting-sort pass per digit.

#include <stdio.h>
 
/* one stable counting-sort pass on the decimal digit that has the value place (1, 10, 100) */
static void pass_by_digit(int a[], int n, int place) {
    int count[10] = {0}, out[16];
    for (int i = 0; i < n; i++) count[(a[i] / place) % 10]++;
    for (int d = 1; d < 10; d++) count[d] += count[d - 1];
    for (int i = n - 1; i >= 0; i--) out[--count[(a[i] / place) % 10]] = a[i];
    for (int i = 0; i < n; i++) a[i] = out[i];
}
 
int main(void) {
    int a[8] = {493, 217, 826, 305, 118, 652, 270, 903};
    printf("start     ");
    for (int i = 0; i < 8; i++) printf(" %3d", a[i]);
    printf("\n");
    int place = 1;
    for (int d = 1; d <= 3; d++, place *= 10) {
        pass_by_digit(a, 8, place);
        printf("digit %d   ", d);
        for (int i = 0; i < 8; i++) printf(" %3d", a[i]);
        printf("\n");
    }
    return 0;
}

start      493 217 826 305 118 652 270 903
digit 1    270 652 493 903 305 826 217 118
digit 2    903 305 217 118 826 652 270 493
digit 3    118 217 270 305 493 652 826 903

In the first pass $493$ and $903$ have the same units digit and stay in the order $493, 903$; that is stability at work.

Cost. Each of the $d$ passes is a counting sort with $k = b - 1$: $\Theta(d (n + b))$ in total. Choosing the base: $n$ numbers each below $n^c$ can be written with $c$ digits in base $n$, so radix sort takes $c$ passes of $\Theta(n)$: $\Theta(c\,n)$, linear for constant $c$. For example $n$ integers in $0 \ldots n^2 - 1$ take two passes in base $n$, while plain counting sort would take $\Theta(n^2)$. For $w$-bit keys and digits of $r$ bits the cost is $\Theta\big(\tfrac{w}{r}(n + 2^r)\big)$.

If an unstable digit sort were used, the order produced by earlier passes would be destroyed and the result could be wrong. (Most-significant-digit-first variants exist; they recurse on groups of equal leading digits and do not need the same stability argument.)

Bucket sort

If the $n$ keys are drawn independently and uniformly from $[0, 1)$, each bucket receives about one key. With insertion sort inside the buckets the expected time is $\Theta(n)$: the expected cost of a bucket with $m$ keys is $\Theta(m^2)$ and the expected value of $m^2$ for a bucket is a constant (about $2 - 1/n$). The worst case is $\Theta(n^2)$ (all keys fall into one bucket) if insertion sort is used inside. It is stable if the buckets are stable lists and the sort inside is stable. It depends on the distribution of the input, not only on $n$.

Summary.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The upper bounds that match this lower bound are merge sort and heap sort; quicksort matches it on average (quicksort). Stability, which makes radix sort correct, is compared across algorithms in stability and comparison of sorts. The idea of using the key value as an index is the idea of hashing.

PYQs

Self-check

Revision card

References