DSA Sorting

Radix Sort

Product SKUs are 12-digit codes. Comparison sorting pays n log n; digit-by-digit sorting pays a few linear passes if each digit has a small alphabet.

Radix sort orders keys one digit (or bit group) at a time. radix needs a such as counting sort. As a , time is Theta(d(n + r)) under those domain assumptions; negatives need an explicit encoding.

Algorithm journey

Fix the digit model

Choose base r and width d (or stop when higher places are zero).

Stable digit pass

Counting-sort on the current place.

Least significant first

Stability carries earlier passes forward.

Handle signs carefully

Shift or bucket negatives; do not pretend two's complement digits are free.

What actually happens

Naive idea: comparison-sort huge integers. Correct; ignores digit structure.

Better idea: stable pass per digit. Domain assumptions (nonnegative keys or an encoding, bounded digit alphabet) are mandatory.

It fails when stability is broken between passes, when d is huge, or when you treat signed bits as unsigned digits without a plan.

Invariant

After processing places 0..p (LSD), records are sorted by the length-(p+1) least-significant digit string; equal prefixes retain prior relative order because each pass is stable.

How to choose radix sort

1. Keys are integers/strings with small digit alphabets? Radix is a strong linear-ish candidate.

2. Need comparison-sort generality? No; stick to merge/Tim/Intro.

3. Memory for count buffers of size r? Must be affordable per pass.

Quantitative check

n = 10^7 thirty-two-bit keys, base 256: d = 4 passes, each Theta(n + 256). Roughly a handful of linear scans, often faster than comparison sorts when memory bandwidth cooperates.

The anatomy of a radix

Base b

The number of possible digit values. Decimal uses 10; byte-wise radix uses 2⁸ = 256 buckets.

Digit count d

The number of passes. For nonnegative maximum U, d = ⌊log_b U⌋ + 1 when U > 0.

Stable inner sort

Counting sort or FIFO buckets order one digit without destroying the order already established by less-significant digits.

Interactive: change the base

Compare base 10 with base 4. A larger base creates more buckets but fewer digit passes. Highlighted digits drive the current pass; bucket entries retain arrival order.

LSD radix pass laboratory

The previous ordering must survive the next digit

Letters are payload. The duplicate records 7B and 7G make stability visible throughout every pass.

Bucket count

b = 10

Digit passes

d = 2

Per-pass work

n + 10

Original order

Snapshot 1 / 3

Array after collection

29A

decimal 29

07B

decimal 7

18C

decimal 18

03D

decimal 3

25E

decimal 25

12F

decimal 12

07G

decimal 7

Stable digit buckets

FIFO within a bucket; collect by bucket number

Start in base 10. Each pass groups by one digit while preserving arrival order inside every bucket.

Base trade-off

Base 10 uses 10 counters and 2 passes here. A larger base spends more auxiliary space to inspect more bits per pass.

Original interactive radix-sort visualizer (retained)

Step through the original decimal-bucket animation to see distribution and collection across every digit place.

Speed:

ℹ️ Ready

Array

Buckets (0-9)

LSD correctness is an invariant across passes

After pass 1

Records are ordered by the least-significant digit. Records with equal digits retain their input order because the pass is stable.

Inductive step

Assume records are ordered by the lowest p digits. A stable sort on digit p + 1 groups that digit, while preserving the lower-digit order inside each group.

After pass d

The order is lexicographic from most- to least-significant digit, which is exactly numeric order for equal-width, nonnegative positional keys.

Why an unstable pass fails: after the ones pass, [11, 12] is correctly ordered. Both tens digits are 1. An unstable tens pass may swap them to [12, 11], erasing the only digit that distinguishes them.

LSD and MSD are different algorithms

Question	LSD: least significant first	MSD: most significant first
Structure	Stable whole-array pass for every position.	Partition by the current digit, then recurse inside each bucket.
Best fit	Fixed-width integers, tuples, and records with a known sequence of keys.	Variable-length strings and keys that often differ near the front.
Stability need	Every digit pass must be stable for correctness.	Recursive refinement supplies correctness; stability is separate if the final contract requires it.
Early exit	Usually processes every required position.	Can stop on singleton/small buckets or end-of-string sentinels.
Operational cost	Predictable sequential scans; easy to implement iteratively.	Recursion, bucket boundaries, and skew need more care.

Treating missing leading digits as zero works for nonnegative integers. Lexicographic strings instead need an explicit end-of-string symbol ordered before real characters; blindly zero-padding strings changes their order.

A stable LSD implementation

The inner counting pass costs Θ(n + b). The Python wrapper demonstrates one signed-value strategy: subtract the minimum before sorting. In fixed-width languages, perform that normalization in a wider or unsigned type to avoid overflow.

Python

python

def stable_digit_pass(values, place, base):
    count = [0] * base
    for value in values:
        digit = (value // place) % base
        count[digit] += 1

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

    output = [0] * len(values)
    for value in reversed(values):       # stability is essential
        digit = (value // place) % base
        count[digit] -= 1
        output[count[digit]] = value
    return output


def radix_sort_nonnegative(values, base=256):
    if base < 2:
        raise ValueError("base must be at least 2")
    if any(value < 0 for value in values):
        raise ValueError("use nonnegative keys")
    if not values:
        return []

    result = list(values)
    maximum = max(result)
    place = 1
    while maximum // place > 0:
        result = stable_digit_pass(result, place, base)
        place *= base
    return result


def radix_sort_signed(values, base=256):
    """Normalize signed Python integers without overflow."""
    if not values:
        return []
    low = min(values)
    shifted = [value - low for value in values]
    return [value + low for value in radix_sort_nonnegative(shifted, base)]

Java

java

import java.util.Arrays;

class RadixSort {
    static int[] sortNonNegative(int[] input) {
        return sortNonNegative(input, 256);
    }

    static int[] sortNonNegative(int[] input, int base) {
        if (base < 2) throw new IllegalArgumentException("base < 2");
        int[] values = Arrays.copyOf(input, input.length);
        int maximum = 0;
        for (int value : values) {
            if (value < 0) throw new IllegalArgumentException("negative key");
            maximum = Math.max(maximum, value);
        }

        int[] output = new int[values.length];
        for (long place = 1; maximum / place > 0; place *= base) {
            int[] count = new int[base];
            for (int value : values) {
                int digit = (int) ((value / place) % base);
                count[digit]++;
            }
            for (int d = 1; d < base; d++) count[d] += count[d - 1];

            // Reverse traversal makes this digit pass stable.
            for (int i = values.length - 1; i >= 0; i--) {
                int digit = (int) ((values[i] / place) % base);
                output[--count[digit]] = values[i];
            }
            System.arraycopy(output, 0, values, 0, values.length);

            // Avoid overflow in place *= base.
            if (place > maximum / base) break;
        }
        return values;
    }

    static int[] sortSigned(int[] input) {
        return sortSigned(input, 256);
    }

    static int[] sortSigned(int[] input, int base) {
        if (input.length == 0) return new int[0];
        if (base < 2) throw new IllegalArgumentException("base < 2");

        int minimum = input[0];
        for (int value : input) minimum = Math.min(minimum, value);

        // Widen before subtracting: the normalized range may exceed int.
        long[] values = new long[input.length];
        long maximum = 0;
        for (int i = 0; i < input.length; i++) {
            values[i] = (long) input[i] - minimum;
            maximum = Math.max(maximum, values[i]);
        }

        long[] output = new long[values.length];
        for (long place = 1; maximum / place > 0; place *= base) {
            int[] count = new int[base];
            for (long value : values) {
                int digit = (int) ((value / place) % base);
                count[digit]++;
            }
            for (int d = 1; d < base; d++) count[d] += count[d - 1];
            for (int i = values.length - 1; i >= 0; i--) {
                int digit = (int) ((values[i] / place) % base);
                output[--count[digit]] = values[i];
            }
            System.arraycopy(output, 0, values, 0, values.length);
            if (place > maximum / base) break;
        }

        int[] result = new int[input.length];
        for (int i = 0; i < values.length; i++) {
            result[i] = (int) (values[i] + minimum);
        }
        return result;
    }
}

Signed values and other key types

Offset by the minimum

Transform x to x − min, sort the nonnegative keys, then restore min. It is simple and stable, but fixed-width subtraction may overflow unless widened.

Flip the sign bit

For fixed-width two's-complement integers, reinterpret the key after flipping its most-significant sign bit, then process all bit groups as unsigned. Negatives map before nonnegatives without reversal.

Partition by sign

Sorting negative magnitudes and reversing them gives numeric order, but a raw reversal also reverses equal-key records and breaks stability. Group equal magnitudes or use a monotone key transform instead.

Strings, tuples, and floats

Strings need alphabet buckets plus an end sentinel. Tuples can be processed from last field to first with stable passes. IEEE floats require a careful sortable bit transform, including policies for −0 and NaN.

Complexity: b and d are not constants by magic

Time

Θ(d(n + b))

Each of d passes scans n records and initializes/accumulates b buckets.

Auxiliary space

Θ(n + b)

One output buffer plus the count or bucket table; buffers can be reused between passes.

Digit count

⌈w / r⌉

For w-bit keys processed r bits at a time, base b = 2ʳ and d = ⌈w/r⌉.

The shorthand O(dn) assumes a fixed base, so b is constant. The shorthand O(n) additionally treats the key width, and therefore d, as fixed. State those assumptions when analyzing the algorithm.

Choosing the base

Base	32-bit passes	Counter table	Trade-off
10	Up to 10	10 counters	Readable for teaching; division/modulo and many passes make it uncommon for binary machine keys.
2⁸ = 256	4	256 counters	A common practical balance: byte extraction is cheap and the table is cache-friendly.
2¹⁶ = 65,536	2	65,536 counters	Fewer record scans, but clearing and prefix-scanning a larger table can dominate or miss cache.

The fastest base depends on n, key width, cache size, memory bandwidth, and implementation. Larger is not automatically better: the + b term must be amortized over enough records.

Where radix sort beats, or loses to: comparison sorting

Strong territory

Large batches of fixed-width integers or fixed-size identifiers.
A small, cache-friendly number of passes over contiguous memory.
Stable record sorting where keys can be extracted cheaply.
Parallel or external-memory designs built around predictable distribution passes.

Comparison sort may win

Small inputs, where setup and extra passes outweigh asymptotics.
Very wide or variable-length keys that require many digit inspections.
Expensive payload movement, limited auxiliary memory, or poor locality.
General comparators whose semantics cannot be encoded as positional digits.

The Ω(n log n) lower bound applies to comparison-only algorithms. Radix sort uses digit extraction and a bounded alphabet, so its relevant cost includes key width: Θ((w/r)(n + 2ʳ)). If w grows, “linear” is no longer a complete description.

Implementation pitfalls

Unstable digit pass: it silently destroys lower-digit ordering.
Place-value overflow: guard before multiplying place *= base.
Negative division rules: modulo of negatives differs across languages; normalize keys deliberately.
Needless allocations: reuse two n-element buffers and swap their roles each pass.
Leading-zero assumptions: valid for numeric magnitude, not automatically for variable-length text.
Base too large: clearing and scanning mostly empty buckets can dominate the input scan.

Exercises

Why must each LSD pass be stable? Give a two-digit counterexample if an unstable pass is used.
Compare counting sort alone vs radix when keys are in [0, 10^9) with n = 10^6.
How would you radix-sort signed 32-bit ints without corrupting order around zero?

Primary sources

Cormen et al., Introduction to Algorithms (CLRS): radix sort.
Knuth, The Art of Computer Programming, Vol. 3: radix exchange and straight radix sorting.
Programming language docs for byte-wise integer sorting utilities where applicable.

Decision rule

Use LSD radix sort when keys have a bounded positional representation, a stable digit pass is cheap, and d(n + b) plus n + b storage beats the simpler comparison-sort alternative. Use MSD when prefixes can divide variable-length keys and let large parts of the suffix go unexamined.