Radix Sort:Digit Passes When Comparison Is the Wrong Primitive

A reconciliation job sorts two million twelve-digit account numbers as String with Arrays.sort. Each compare walks characters until a difference. Staging with twenty thousand rows looks fine. Production still asks “is this key less than that key?” millions of times on keys that are digits in fixed positions.

Nobody wrote a bad Comparable. They used comparison on a key that already has a digit layout.

Radix sort is a counting-sort pass per digit: after d stable digit passes, the keys are ordered without asking which key is smaller. Comparison is the wrong primitive when the keys are integers or fixed-width strings. The Algorithms Roadmap owns families and the glossary. Here we only care about digit passes, counting sort as the subroutine, and why Java Arrays.sort is not this.

Comparison vs a digit layout

A comparison sort’s only question is a < b. That is correct for a Comparator over two fields, a locale-aware name, or a key you cannot split. Account numbers, IPv4 addresses packed in 32 bits, 64-bit request ids, padded numeric strings: the key is a sequence of digits (or bytes). You can sort on the least significant digit, then the next, then the next, and the whole key ends up ordered.

Each pass must be stable. After you sort on the ones place, two numbers that share a ones digit must keep the order the previous pass (or the input) already set. Counting sort that places from the right is that pass. Unstable place-from-the-left would scramble the higher digits you have not processed yet — or, in LSD, the lower digits you already finished.

Note: Radix is not “counting sort but bigger.” Counting sort needs a small universe for the whole key. Radix needs a small universe for one digit (k = 10 decimal, k = 256 for a byte) and repeats. A 32-bit id is a terrible counting-sort key and a fine four-byte radix key.

LSD: least-significant digit first

LSD processes the least significant digit first, then the next more significant, until the most significant. After pass d, the keys are sorted on the last d digits. The final pass is the high digit; the array is sorted on the whole key.

Fixed width is the LSD-friendly layout: pad account numbers on the left with zeros, or treat an int as four bytes. Variable-length strings can still LSD if you pad; they often prefer MSD (below) so you do not invent padding.

Walk eight three-digit values. Decimal digits, k = 10. Each pass is a stable counting sort on that place.

input:
  170  045  075  090  002  024  802  066

pass 1 — ones:
  0: 170, 090
  2: 002, 802
  4: 024
  5: 045, 075
  6: 066
  →  170  090  002  802  024  045  075  066

pass 2 — tens:
  0: 002, 802
  2: 024
  4: 045
  6: 066
  7: 170, 075
  9: 090
  →  002  802  024  045  066  170  075  090

pass 3 — hundreds:
  0: 002, 024, 045, 066, 075, 090
  1: 170
  8: 802
  →  002  024  045  066  075  090  170  802

After ones, 170 still sits left of 075 even though both end in a digit that will later move. Tens keep 002 left of 802 (same tens digit 0). Hundreds separate them. Three linear counting-sort passes, no a < b.

Drop stability on pass 1 and the later passes cannot recover. Suppose 170 and 090 both have ones-digit 0, and an unstable pass reverses them to 090, 170. Tens then sees 9 vs 7 and will order by tens only: 170 before 090 — which happens to look fine — but 002 and 802 share tens-digit 0; reverse them on the ones pass and the hundreds pass is sorting a pair whose low digits are already wrong. LSD only works because each pass preserves the order already won on less-significant digits.

The invariant: after pass p (0 = least significant), the array is sorted on digits 0 .. p. Pass p+1 may move items across buckets of digit p+1, but items that share that digit stay in the order pass p left them.

MSD, briefly

MSD starts at the most significant digit, partitions into k buckets, and recurses on each bucket. A bucket that holds one item is done. Variable-length strings fit this shape: you inspect the next character only inside a bucket that still has a tie, like a trie walk.

LSD is the default for fixed-width integers: d is known, every pass is the same counting-sort loop, no recursion. MSD is the name to recognize for strings of uneven length. This post’s Java is LSD.

	LSD	MSD
First digit	Least significant	Most significant
Recursion	No — d identical passes	Yes — per bucket
Best fit	Fixed-width ints, padded accounts	Uneven strings
Needs stable pass	Yes	Partitioning; different sketch

A packed IPv4 (int in host order) is four LSD byte passes — the same loop as the sketch below. A 64-bit request id is eight. Do not convert those ids to String so Arrays.sort can compare characters; that is the reconciliation-job complaint with extra allocations.

Java sketch: four byte passes on int

Treat each int as four unsigned bytes. Digit universe k = 256. Four counting-sort passes, shift 0, 8, 16, 24. Place from the right. Swap the buffers so the next pass reads what the last pass wrote.

static void lsdRadixSort(int[] a) {
    int n = a.length;
    int[] out = new int[n];
    int[] count = new int[256];
    for (int shift = 0; shift < 32; shift += 8) {
        Arrays.fill(count, 0);
        for (int v : a) {
            count[(v >>> shift) & 0xFF]++;
        }
        for (int i = 1; i < 256; i++) {
            count[i] += count[i - 1];
        }
        for (int i = n - 1; i >= 0; i--) {
            int digit = (a[i] >>> shift) & 0xFF;
            count[digit]--;
            out[count[digit]] = a[i];
        }
        int[] tmp = a;
        a = out;
        out = tmp;
    }
}

Four passes is even, so after the last swap the sorted data sits in the original array object the caller passed. (The local a reference ping-pongs; the even write lands back on the caller’s storage.) >>> and 0xFF pick a byte without a sign-extending shift. Empty input and n == 1 are no-ops: the loops run, the single slot copies onto itself.

id = 0x12_34_56_78
  shift  0  → digit 0x78
  shift  8  → digit 0x56
  shift 16  → digit 0x34
  shift 24  → digit 0x12

Note: This sketch orders the bits as unsigned. Integer.MIN_VALUE sorts among the high unsigned values, not as “smallest signed int.” Signed order is a transform (flip the sign bit on the last pass, or offset). Do not ship this loop as a drop-in replacement for Arrays.sort on mixed negative int[] until that transform is explicit.

Twelve-digit account numbers as char[] or digit bytes are the same loop with k = 10 and d = 12. Digit p from the right (0 = ones) on a long:

static int digit(long n, int p, long[] pow10) {
    return (int) ((n / pow10[p]) % 10L);
}

Precompute pow10[0] = 1, pow10[i] = 10 * pow10[i - 1]. Or store digits[width - 1 - p] if you already split. Left-pad shorter strings to width d; LSD on mixed lengths without padding compares the wrong place values.

Complexity

d passes, each a counting sort on universe k.

Time	O(d (n + k))
Extra space	O(n + k) — buffer plus histogram
Stable	Yes, if every pass is
In-place	Not in this formulation
Key comparisons	None

Byte-wise 32-bit: d = 4, k = 256. Byte-wise 64-bit: d = 8. Decimal account numbers: d = 12, k = 10. The constant d is why this beats O(n log n) comparison when n is large and the width is fixed. When n is tiny, d full passes lose to one Timsort of a short array.

A rough crossover: d (n + k) against n log₂ n. For d = 4, k = 256, the linear side is already ahead by tens of thousands of rows; at two million account numbers it is not a close call. Do not micro-benchmark a dozen keys and declare radix faster.

The extra buffer is one n-array plus a k-histogram you reuse every pass. You can ping-pong two buffers instead of allocating per pass. You cannot skip the buffer and overwrite a in the same counting-sort pass.

When not to use radix sort

Skip digit passes when there are no digits, or the comparison sort is already the cheaper honest line:

• Tiny n. A dozen account numbers. Arrays.sort is the one-liner.
• Already comparison-sorted objects with no digit layout. A List<Invoice> Timsort already ordered by a Comparator of two fields. There is nothing to split into bytes. Re-running LSD on a field you have not digitized is cargo-cult of the name.
• No digit layout. A display name, a locale-aware String, a key you cannot split into a small alphabet. Comparison is the primitive.
• Already the JDK default. Java Arrays.sort is not radix. Object arrays run Timsort. Primitive int[] runs Dual-Pivot Quicksort. Do not “optimize” a call that is already those procedures by renaming it.
• Floating point, unless you encode bits on purpose. Raw double / float bits are not a monotonic digit layout: sign, exponent, and NaN pay for a transform (IEEE sign-magnitude). Mention it; do not invent a float radix in the reconciliation job. If you have not written that encoding, call Arrays.sort.

Radix sort is for keys that are digit strings. It is not a faster Timsort.

JDK: Arrays.sort is not radix

There is no java.util.RadixSort. The library map on the hub still holds:

• Object arrays / lists: Arrays.sort / List.sort — Timsort
• Primitive arrays: Arrays.sort — Dual-Pivot Quicksort

You write LSD (or MSD) when the key has a digit structure and n is large enough that d counting-sort passes beat comparison. You do not hand-roll radix for a List<Invoice> ordered by a BigDecimal you have not digitized, and you do not claim the JDK already did it. Collections.sort is still Timsort. IntStream.sorted() is still comparison.

Call Arrays.sort unless the key is digits or bytes and you mean to run counting sort d times.

The subroutine is the previous post. If the place pass is not stable, none of the LSD walk above is a sort. An odd d (three decimal digits, seven-bit codes) leaves the last write on the buffer: copy out back, or ping-pong one extra pass. Four byte passes dodge that copy.

Cheat sheet

Job:        sort keys that are digits/bytes (ints, padded strings, packed IPs)
Shape:      LSD default for fixed width; MSD named for uneven strings
Each pass:  counting sort on one digit (k = 10 or 256), place from the right
Time:       O(d (n + k))     extra space: O(n + k)
Stable:     required of every pass
Not this:   tiny n; Comparator objects; Arrays.sort; raw IEEE floats
JDK:        no RadixSort; Arrays.sort is Timsort / Dual-Pivot Quicksort

Do:

• Run LSD on a fixed-width integer or padded digit string; reuse counting sort per digit.
• Keep each pass stable so earlier digits survive later ones.
• Treat d and k as part of the bill, not as free constants.
• Pad fixed-width strings (or pack ints as bytes) so every key has the same d.

Don’t:

• Claim Arrays.sort is radix on objects or on int[].
• Skip the transform and radix-sort raw double bits.
• Use an unstable digit pass and then debug “almost sorted” output.
• Convert a packed int id to String so comparison sort can walk characters.

Wrap-up

Radix sort is d counting-sort passes over a digit alphabet. LSD walks least-significant first on a fixed-width key; MSD is the brief other name for variable-length strings. Comparison never runs. The subroutine is counting sort, including place-from-the-right. Java Arrays.sort remains Timsort on objects and Dual-Pivot Quicksort on primitives — not this.

Use it when account numbers, packed addresses, or integer ids are the key and n is large. The two-million-row reconciliation of twelve-digit accounts is this procedure: pad, twelve counting-sort passes. Two hundred rows is Arrays.sort. A Comparator over payee name plus amount is never this algorithm. Skip it when n is tiny, the key has no digits, or you have not encoded the bits. The next post is what the JDK actually runs when you sort objects.

Next optional step in the series What Arrays.sort actually runs on objects. Timsort: What Arrays.sort Actually Runs on Objects →