DSA Complexity

Radix sort cost

A compiler sorts millions of 64-bit immediates. Comparison sorts pay n log n; byte-wise radix pays a constant number of linear passes.

Budget under a clear . LSD requires stable passes. This is non-comparison complexity: valid only when keys fit the encoding.

Algorithm journey

Choose r and d

Bytes: r=256, d=4 or 8 for 32/64-bit.

Pay n + r per pass

Counting-sort digit pass.

d passes

LSD order.

Multiply

Theta(d(n + r)).

What actually happens

Naive claim: radix is always linear in n. Incomplete without d and r.

Better claim: fix width and base, then compare d(n+r) to n log n.

Fails if d grows with key length unboundedly, or if passes are unstable.

Invariant

After i stable LSD passes, order is correct by the length-i least-significant digit string; total cost sums i independent linear passes.

How to read radix sort's complexity

1. Fixed-width integers? Often wins.

2. Arbitrary comparable objects? Out of model.

3. Huge r? Pass buffers hurt; pick a smaller base.

Quantitative check

n = 10^7, 32-bit keys, r = 256, d = 4: about 4 linear passes over 10^7 plus tiny 256-sized tables. Compare to ~n log2 n ≈ 2.3 x 10^8 comparisons for a comparison sort (plus constant factors).

How it works (LSD)

Find Max Number

Determine the maximum number to know how many digits (k) we need to process.

Sort by Each Digit

Start from the Least Significant Digit (ones place). Use a stable sort (like Counting Sort) to sort the array based on this digit.

Repeat

Move to the next digit (tens, hundreds, etc.) and repeat until the most significant digit is processed.

🎮 Interactive Radix Sort Demo

Watch how numbers are grouped into buckets based on their current digit (ones, tens, hundreds)!

Speed:

ℹ️ Ready

Array

Buckets (0-9)

💡 Pro Tip: Base Matters!

Radix sort usually works in Base 10 (digits 0-9), but it's even faster in Base 2 (binary) or Base 256 (bytes). Computers love bitwise operations!

💻 Implementation

Python

python

def radix_sort(values: list[int]) -> None:
    """Stable LSD radix sort for signed integers; mutates values."""
    if len(values) < 2:
        return

    minimum = min(values)
    max_key = max(values) - minimum
    output = [0] * len(values)
    exp = 1

    while max_key // exp > 0:
        count = [0] * 10

        for value in values:
            digit = ((value - minimum) // exp) % 10
            count[digit] += 1

        for digit in range(1, 10):
            count[digit] += count[digit - 1]

        # Right-to-left placement is what preserves stability.
        for i in range(len(values) - 1, -1, -1):
            digit = ((values[i] - minimum) // exp) % 10
            count[digit] -= 1
            output[count[digit]] = values[i]

        values[:] = output
        exp *= 10


data = [170, -45, 75, 0, -802, 24, 2, 66]
radix_sort(data)
assert data == sorted(data)
print(data)

Java

java

import java.util.Arrays;

public class RadixSort {
    /** Stable LSD radix sort for every signed int value. */
    static void radixSort(int[] values) {
        if (values.length < 2) return;

        int minimum = values[0];
        int maximum = values[0];
        for (int value : values) {
            minimum = Math.min(minimum, value);
            maximum = Math.max(maximum, value);
        }

        // long avoids overflow for MAX_VALUE - MIN_VALUE and exp *= 10.
        long maxKey = (long) maximum - minimum;
        int[] output = new int[values.length];

        for (long exp = 1; maxKey / exp > 0; exp *= 10) {
            int[] count = new int[10];
            for (int value : values) {
                long key = (long) value - minimum;
                count[(int) ((key / exp) % 10)]++;
            }
            for (int digit = 1; digit < 10; digit++) {
                count[digit] += count[digit - 1];
            }
            for (int i = values.length - 1; i >= 0; i--) {
                long key = (long) values[i] - minimum;
                int digit = (int) ((key / exp) % 10);
                output[--count[digit]] = values[i];
            }
            System.arraycopy(output, 0, values, 0, values.length);

            // maxKey for int inputs is below 10^10, so the next multiply is safe.
        }
    }

    public static void main(String[] args) {
        int[] data = {170, -45, 75, 0, -802, 24, 2, 66};
        radixSort(data);
        System.out.println(Arrays.toString(data));
    }
}

🧠 Invariant, Key Domain, and Engineering Trade-offs

Pass invariant

After processing exponent exp, records are ordered by every digit through that position. A stable bucket pass keeps the ordering established by less-significant digits; induction over the passes proves the final order.

Signed values

Decimal digit extraction is not directly valid for negative remainders. The implementation shifts each key by the minimum using a wider integer, so all logical keys are non-negative without changing their relative order.

Choose the radix

Base 10 teaches the mechanism. Production integer sorts often use byte-sized digits (base 256): fewer passes than binary and a count table that usually fits comfortably in cache.

Production checklist

Define the key type and ordering first; variable-length strings need terminator rules.
Budget O(n + b) auxiliary memory and reject a base that makes the count table impractical.
Test empty, singleton, duplicate-heavy, all-negative, and extreme integer inputs against the library sort.
Prefer the language library unless profiling proves fixed-width key sorting is the bottleneck.

A stable pass, traced with duplicate identities

The suffixes a and b distinguish equal records. Right-to-left placement into cumulative-count positions preserves their encounter order; that is the mechanism LSD correctness depends on.

Stable least-significant-digit radix trace
State	Order	Invariant gained
Input	21a, 11, 22, 12, 21b	No digit guarantee yet
Ones pass	21a, 11, 21b, 22, 12	Ordered by the last digit; equal ones retain input order
Tens pass	11, 12, 21a, 21b, 22	Ordered by both processed digits; duplicate 21 records remain stable

Induction: before pass p, records are ordered by digits 0…p−1. A stable sort by digit p groups that digit without disturbing the established lower-digit order inside each group. After the most significant digit, full keys are ordered.

LSD, MSD, and key-domain decisions

LSD and MSD radix sort comparison
Dimension	LSD radix	MSD radix
Direction	Least to most significant; every pass must be stable	Partition by most significant digit, recurse within buckets
Natural fit	Fixed-width integers and equal-length keys	Strings/prefix keys; can stop buckets that become uniform
Main risk	Unstable digit pass silently corrupts prior ordering	Skewed buckets, recursion, and explicit end-of-key ordering
Adaptivity	Usually processes all required positions	May avoid examining long suffixes after decisive prefixes

For strings, define alphabet, normalization, collation, and an end-of-key sentinel that sorts before any continuing character. Byte order is not automatically user-visible Unicode order. For signed fixed-width two's-complement integers, another production technique flips the sign bit of the most-significant byte so unsigned byte order matches signed numeric order.

The real complexity parameters

passes

d = ⌈log_b(W + 1)⌉

W is shifted key range; fixed machine words cap d.

one stable pass

Θ(n + b)

Count/scan n records and prefix-sum b buckets.

whole sort

Θ(d(n + b))

Auxiliary storage is Θ(n + b).

Radix sort does not violate the Ω(n log n) comparison-sort lower bound: it is not comparison-only and assumes keys expose bounded digits. Base b trades fewer passes against a larger count table, zeroing cost, and cache pressure. Base 256 is common for bytes; the best choice is hardware and workload dependent.

Adversarial tests and production guardrails

• Empty/singleton, all equal, all negative, mixed signs, zeros, and duplicate identities.
• MIN_VALUE and MAX_VALUE together to expose subtraction and exponent overflow.
• Keys differing only in the highest processed digit and long common prefixes.
• Property-test sortedness, permutation, and stability against a trusted stable sort.

• Reuse output/count buffers and measure memory bandwidth, not only comparisons.
• Keep payload records stable by moving indices/references with keys, not keys alone.
• Parallel buckets require deterministic prefix offsets; naive shared appends contend.
• Prefer a library sort until profiling shows fixed-width key throughput is a bottleneck.

⚡ Complexity Analysis

Time Complexity

✓
O(d * (n + b))
d = digits, n = elements, b = base (10)
Often simplified to O(nk) or O(n) if d is small constant.

Space Complexity

⚠
O(n + b)
Need output array + count array

Other Properties

✓Stable: Must be stable for LSD to work
✗Not In-place: Requires extra space

✅ Pros & ❌ Cons

✅ Advantages

✓Linear time O(n) when digits are constant
✓Can outperform comparison sorts for large fixed-width integer workloads after profiling

❌ Disadvantages

✗Only works for integers/strings (fixed length keys)
✗High space complexity O(n)
✗Slower in practice for small inputs due to overhead

Exercises

For 64-bit keys and r=256, what is d? Rewrite total cost.
Show numerically when d(n+r) beats c n log n for c≈2.
Why does MSD radix have a different practical cost profile than LSD even with similar asymptotics?

Primary sources

CLRS: radix sort.
Knuth TAOCP Vol. 3: radix sorting.
Engineering notes on byte-wise integer sorting in DB/engine codebases.

Short takeaway

Radix Sort = Sort digit-by-digit (LSD).Time: O(nk).Space: O(n+k).Use when: Sorting integers or fixed-length strings.Key: Uses a stable sub-sort (like Counting Sort).