Radix Sort Algorithm

Radix Sort sorts integers without comparing them: it repeatedly buckets numbers by one digit position at a time using a stable counting-sort pass, so that by the time the most significant digit has been processed the whole array is ordered — the trick being that stability lets the ordering established by earlier (less significant) digits survive intact through every later pass.

Recognize the pattern

• Input is fixed-width keys — non-negative integers, or fixed-length strings — not arbitrary comparable objects.
• The problem hints at a small, bounded alphabet/base (digits 0–9, bytes 0–255, lowercase letters) and asks for better than O(n log n).
• Range of values is much larger than the digit-count, e.g. sorting a million numbers each up to 10 digits, so per-digit buckets stay cheap relative to n.
• Phrasing like "sort n integers, each ≤ 10^9" or "sort fixed-length strings" is the tell for LSD radix sort.

Brute force → optimal

Brute force: a comparison sort (Merge/Quick/Heap Sort) treats each key as opaque and compares whole keys pairwise — O(n log n) comparisons, and comparing two d-digit numbers itself costs O(d), giving O(n·d·log n) overall.

Optimal — Radix Sort: never compares two full keys directly. It runs d passes, each a stable Counting Sort over a single digit in base b (e.g. b = 10). Total work O(d·(n + b)) — linear in n for fixed d and b, which beats the Ω(n log n) lower bound that only binds comparison-based sorts.

Complexity, derived from first principles

Let n = elements, d = digits in the largest element, b = radix (base).

• One digit pass (Counting Sort): O(n) to tally occurrences into a count array of size b, O(b) to turn counts into cumulative/prefix positions, O(n) to scan the input in reverse and place each element at its computed output index. Total per pass = O(n + b).
• d passes (one per digit, LSD to MSD): total time O(d·(n + b)).
• Since d = ⌈log_b(max)⌉, this is O(n·log_b(max)) — for 32-bit ints with b=10, d ≤ 10, effectively O(n) with a small constant.
• Space: O(n + b) — an output array of size n plus a count array of size b, reused per pass. Not in-place, unlike Quicksort.

Traced worked example

Input: [180, 55, 85, 90, 903, 243, 2, 6]. Max = 903 → d = 3 digits, so 3 counting-sort passes (exp = 1, 10, 100).

Pass 1 detail (units digit): in input order the units digits are 0,5,5,0,3,3,2,6 for 180,55,85,90,903,243,2,6 — count array [2,0,1,2,0,2,1,0,0,0] (index = digit, e.g. two numbers end in 0: 180 and 90). Cumulative sums give the final slot for each digit; scanning the input right to left and placing each number at count[digit]-1 then decrementing preserves relative order among equal digits — that's what makes the whole algorithm work.

Pass 2 detail (tens digit), applied to Pass 1's output [180, 90, 2, 903, 243, 55, 85, 6]: tens digits are 180→8, 90→9, 2→0, 903→0, 243→4, 55→5, 85→8, 6→0. The three numbers with tens digit 0 — 2, 903, 6 — must keep their relative order from the Pass-1 array, giving the sub-sequence (2, 903, 6); the two numbers with tens digit 8 — 180, 85 — must appear as (180, 85), ordered before the single tens-digit-9 number (90) and after tens-digit-4 (243) and tens-digit-5 (55). Concatenating groups by ascending tens digit (0,4,5,8,9) yields [2, 903, 6, 243, 55, 180, 85, 90] — this is the array shown above, and it is what stability guarantees: the units-digit order (2 before 903 before 6, and 180 before 85) survives unchanged inside each tens-digit group.

Java implementation (LSD radix sort, base 10)

public class RadixSort {
    public static void sort(int[] arr) {
        if (arr.length == 0) return;
        int max = arr[0];
        for (int v : arr) if (v > max) max = v;
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortByDigit(arr, exp);
        }
    }

    private static void countingSortByDigit(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10];

        for (int i = 0; i < n; i++) {
            int digit = (arr[i] / exp) % 10;
            count[digit]++;
        }
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }
        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }
        System.arraycopy(output, 0, arr, 0, n);
    }
}

Pitfalls

• Non-negative assumption: the classic algorithm breaks on negative numbers because (v/exp)%10 and array indexing assume digits ≥ 0. Fix by offsetting (shift all values by |min|) or bucketing sign separately.
• Wrong scan direction in the placement step: you must iterate the input in reverse when placing into output using cumulative counts, or stability breaks and the sort silently produces wrong results (not a crash — a subtle bug).
• Confusing LSD with MSD radix sort: LSD (shown here) needs a stable subroutine and processes least-significant digit first; MSD recurses per bucket top digit first and is used for variable-length strings/tries but needs care with equal-length prefixes.
• Large radix or large max value: if b or d is large (e.g. sorting 64-bit longs digit-by-digit in base 10, d≈19), the constant factor can erase the linear-time advantage over an O(n log n) sort with small n.

When to use / when not — vs Comparison Sorts

Use Radix Sort when keys are integers or fixed-length strings with bounded digit count and n is large relative to d — e.g. sorting timestamps, IP addresses, fixed-width IDs. Avoid it for floating-point keys, arbitrary objects with custom comparators, very large key ranges relative to n, or when extra O(n) memory is unacceptable — reach for Quicksort/Merge Sort instead.

Takeaways

• Radix Sort sorts digit-by-digit using a stable Counting Sort subroutine, never comparing two full keys.
• Complexity O(d·(n+b)) time, O(n+b) space — linear in n when d and b are fixed constants.
• Stability of the per-digit pass is the load-bearing property that makes correctness work across passes.
• It only applies to fixed-width, boundedly-based keys — not a general-purpose replacement for comparison sorts.
• Where it shows up: radix sort is the linear-time integer-sort engine that problems like "Maximum Gap" build on — sort n integers in O(d·n) then scan adjacent differences, sidestepping the O(n log n) comparison-sort route.

Recall question: Why must the counting-sort subroutine used inside each digit pass be stable, and what breaks if it isn't?

Synthesized from the original page's step-by-step walkthrough, standard CLRS-style Radix/Counting Sort analysis, and worked-example verification (recomputed by hand, digit by digit, to confirm every intermediate array).