07. Non-Comparison Sorting

Why Comparisons Alone Have a Limit#

With n distinct items there are n! possible input orders. A comparison-based sort must distinguish them. A yes/no comparison gives at most two branches, so a decision tree of depth k has at most 2^k leaves. We need at least n! leaves: 2^k >= n!, hence k >= log₂(n!).

Read each branch as the result of one comparison between labelled items. Two binary comparisons can distinguish at most four outcomes, fewer than the six orders of three distinct values. It is the worst-case depth that must be at least three, not a claim that every input requires the same path length.

For an asymptotic bound, at least half the factors in n! are at least n/2. Thus n! >= (n/2)^(n/2) and log₂(n!) >= (n/2) log₂(n/2) = Ω(n log n). Merge sort matches this growth. The deck's “2^k comparisons” wording should be read as 2^k possible leaves after k binary comparison decisions, not 2^k executed comparisons.

This lower bound assumes sorting learns order only through key comparisons. If keys have a small digit alphabet, we can examine digits and use them as bucket indices. Such an algorithm has more information available per operation and is outside the comparison-only model.

Practice. Does a linear-time radix sort contradict the comparison lower bound? What assumption has changed?

Radix Sort: Order One Position at a Time#

A radix R is the number of possible symbols at one key position. Decimal digits give R=10; an alphabet of lowercase letters has 26 symbols. A key length m is the number of positions. These are different quantities: a six-digit decimal number has m=6, R=10.

The lecture teaches least-significant-digit, or LSD, radix sorting: stably sort on the last position, then the preceding one, continuing towards the first. Each pass distributes whole items into buckets by the current symbol, then concatenates buckets in symbol order. Appending and retrieving in arrival order makes each bucket stable.

For unequal lengths, padding must preserve the desired order. Decimal integers can be left-padded with zeroes. For lexicographically sorted strings, use a conceptual end/padding symbol ordered before real letters and right-pad shorter strings. The lecture's alphabet {a,b,c} needs a fourth bucket for _, so the padded implementation has radix four, even though the original letter alphabet has three symbols.

A Numeric Worked Example#

Start [119,232,034,065], treating each as three digits. On the ones digit, bucket 2 receives 232, 4 receives 034, 5 receives 065, and 9 receives 119. Collection gives [232,034,065,119]. On the tens digit, stable buckets produce [119,232,034,065]. On the hundreds digit, bucket 0 retains 034,065, bucket 1 has 119, bucket 2 has 232; output is [034,065,119,232].

This original numeric custom trace shows every distribution decision and complete bucket state. The values are numeric, so the player shows 34 rather than a leading-zero string; interpret it as the padded key 034.

Each snapshot records authored state. The player's C tab gives the complete decimal pass implementation below, and its complexity panel derives the work for m positions, n items and radix R. The bucket rows display only occupied buckets, while the C code initialises all ten counters each pass. Trace counters would measure only authored events, not every loop operation.

The Lecture String Example#

For abc,cab,baa,a,ca, pad to abc,cab,baa,a__,ca_. Ordered buckets are _, a, b, c.

The final-position distribution is _:[a__,ca_], a:[baa], b:[cab], c:[abc]. Collection gives a__,ca_,baa,cab,abc. Notice that the padding bucket retains a__ before ca_ because that is their arrival order.

The middle pass produces _:[a__], a:[ca_,baa,cab], b:[abc]. Collection remains a__,ca_,baa,cab,abc. A pass can leave the whole sequence unchanged while establishing another ordering property.

The first pass gives a:[a__,abc], b:[baa], c:[ca_,cab]. The final result is a,abc,baa,ca,cab. Padding explains why the prefix word a precedes abc, and ca precedes cab.

Why Stability Makes LSD Work#

After the first pass, keys are sorted by their last symbol. Suppose they are sorted by the last k symbols. The next stable pass sorts by the symbol immediately before those. Different new symbols are correctly grouped; within an equal-symbol group, stability preserves the already correct last-k order. Therefore keys are sorted by the last k+1 symbols. Induction over all m passes gives full order.

Practice. Two-digit input [12,11] becomes [11,12] after sorting by ones. If the tens pass reverses equal-tens items, what happens?

Implement a Stable Digit Pass in C#

The following implementation sorts nonnegative decimal integer keys of a specified digit width. It uses stable counting distribution as the bucket mechanism. This is an implementation detail of the radix pass, not a separate lecture chapter on general counting sort. Require n >= 0, digits >= 0, keys below 10^digits, and a caller-provided out buffer of n integers distinct from a.

#include <stddef.h>

void radixSort(unsigned a[], unsigned out[], size_t n, unsigned digits) {
    unsigned long long place = 1;
    for (unsigned pass = 0; pass < digits; pass++) {
        size_t counts[10] = {0};
        size_t next[10];
        for (size_t i = 0; i < n; i++) {
            unsigned d = (unsigned)((a[i] / place) % 10);
            counts[d]++;
        }
        next[0] = 0;
        for (unsigned d = 1; d < 10; d++) {
            next[d] = next[d - 1] + counts[d - 1];
        }
        for (size_t i = 0; i < n; i++) {
            unsigned d = (unsigned)((a[i] / place) % 10);
            out[next[d]++] = a[i];
        }
        for (size_t i = 0; i < n; i++) a[i] = out[i];
        if (pass + 1 < digits) place *= 10;
    }
}

For the portable teaching contract, use at most ten digits and keys representable by a 32-bit unsigned integer; the wider place avoids a decimal-position overflow. The array count and prefix sums use size_t, the C type intended for sizes and indices. For record keys, copy the complete record rather than just its integer.

counts[d] gives bucket lengths. next[d] initially gives the first output index reserved for bucket d; increment it after writing each incoming item. Scanning input left-to-right and advancing the bucket's output index preserves arrival order. For [21,11,22] on ones, counts for 1 and 2 are two and one, starts are zero and two, and output is [21,11,22]. On tens, output becomes [11,21,22].

Practice. Why cannot this code simply accept negative signed integers by casting them to unsigned?

Derive Costs and Choose the Algorithm#

One pass initialises/scans R buckets and distributes/collects n items, giving Θ(n+R) work. Repeating for m positions gives Θ(m(n+R)). Buckets and temporary output require Θ(n+R) auxiliary storage when entries are references or fixed-size items. If copying a key itself takes m character operations, the representation changes the cost; bucket references avoid repeatedly copying whole variable-length strings.

For fixed m and fixed R, the bound becomes linear in n. If keys grow longer or the alphabet grows, do not discard those variables. A direct bucket for every Unicode code point can waste space and scanning work. Radix is stable with stable passes, non-adaptive because it still processes every configured position, and not in-place in this implementation.

Use it when keys decompose into a small ordered alphabet and the digit/pass count is suitable. Comparison sorting works with a far broader range of key types and custom comparisons. Decimal width, signed values and padding are representation decisions, not details to leave unspecified.

More exam-style practice#

Work each prompt before opening its answer. State the invariant or cost assumption that makes your reasoning valid.

Question 1. Perform a stable ones-digit pass on [21a,12,11b,22], where suffixes label records. Then perform the stable tens-digit pass.

Question 2. For n records, m positions and radix R, give LSD radix-sort time and auxiliary space. When is calling it “linear” misleading?

Question 3. Explain why padding a shorter string with a symbol ordered before every real character is needed in lexicographic LSD sorting.