← SciSim / Computer Science

🔀 Radix Sort

Non-Comparison Sort | LSD/MSD | Digit-by-Digit Stable Passes

Standard Undergraduate

§1 — Interactive Simulation

Speed:
1
Digit Pass
Units
Current Digit
0
Step
8
n
RADIX-SORT(A, d): // d = number of digits
  for i ← 1 to d: // LSD: start from least significant
    STABLE-SORT(A) on digit i // use Counting Sort
// After pass i, array is sorted by last i digits

§2 — The Idea, Step by Step

Imagine sorting a big stack of mail by ZIP code without ever comparing two envelopes to each other. You make ten trays labelled 0 through 9. First you deal every envelope into the tray matching its last ZIP digit, then stack the trays back up in order. You repeat with the next-to-last digit, then the next, and so on. After the last digit, the whole pile is sorted. That trick — sort by one digit at a time, never comparing whole numbers — is Radix Sort.

The quantities that matter are the count of items $n$, the number of digit positions $d$, and the number of buckets $k$ (the radix, which is $10$ for ordinary decimal numbers and $256$ if you treat each byte as a "digit"). One rule drives everything: in each pass you do a single stable bucket sort on one digit, working from the least-significant digit to the most.

Worked pass. Take 170, 45, 75, 90, 2. Sorting only by the units digit (0,5,5,0,2) drops them into trays and reads back as 170, 90, 2, 45, 75. The tens of these numbers are still scrambled — but notice 45 stayed before 75 because the tray kept ties in their original order. That preserved order is exactly what the next pass relies on.

Why "stable" is non-negotiable: when two numbers share the current digit, the pass must keep the order an earlier pass already gave them. If the per-pass sort reshuffled ties, every earlier pass's work would be undone. Counting Sort is the usual engine because it is both stable and $O(n+k)$. With $d$ passes the total cost is $O(d(n+k))$ — linear in $n$ when $d$ and $k$ are fixed, which is how Radix Sort can beat the $O(n\log n)$ floor that binds comparison sorts. The sliders map straight onto the theory: Array Size sets $n$, and Digits sets $d$ (so it also sets how many passes you watch).

Try this in the sim above. First, set Digits to 1 and step through — the array sorts in a single pass, because one digit is all there is. Next, raise Digits to 3 and watch the pink-highlighted column march right-to-left, the array only becoming truly sorted on the final pass. Finally, choose the Many Duplicates preset and step slowly: equal values never swap order, which is the stability property working in front of you.

§3 — Complexity Analysis & Derivation

SymbolMeaning
nNumber of elements
dNumber of digits (or bits per chunk)
kBase/radix (10 for decimal, 256 for bytes)
bTotal bits in a number
Step 1 — One Digit Pass. Each pass uses Counting Sort on digit values 0..k−1. Cost per pass: O(n+k).
Step 2 — Total Passes. d passes needed to process all digits. Total: T = d × O(n+k) = O(d(n+k)).
Step 3 — Choosing Radix k. For b-bit integers with radix k=2^r (sort r bits at a time): d = b/r passes, each O(n + 2^r). Total: O((b/r)(n+2^r)). Optimal r = log₂n → T = O(bn/log n). For 32-bit integers: r=8 (byte-at-a-time), k=256, d=4 passes, T=O(4(n+256))=O(n).
Step 4 — Why LSD (Least Significant Digit) first. LSD with stable sort: after processing digit i, elements are sorted by digits 1..i. Later passes preserve earlier digit ordering for ties (stability). MSD is also valid but requires recursive grouping — simpler to implement recursively.
Step 5 — Stability requirement. The underlying sort MUST be stable. If not, a later digit pass can destroy the ordering established by earlier passes. Counting Sort is used because it is stable and O(n+k).
Step 6 — Space complexity. O(n+k) for the Counting Sort buffer. Radix Sort is NOT in-place.
Step 7 — Comparison with O(n log n) sorts. Radix Sort O(dn) beats O(n log n) when d = O(log n / log log n). For 32-bit integers with n=10⁶: Radix Sort ≈ 4×10⁶ ops vs Quicksort ≈ 20×10⁶. In practice, Radix Sort can be 2–4× faster but has worse cache behavior than Quicksort for large k.

§4 — Frequently Asked Questions

Q1. Why must the sub-sort in each pass be stable?concept▾
Stability ensures that when two numbers have the same digit in the current position, their relative order (established by previous passes on less-significant digits) is preserved. Without stability, the previous passes' work is destroyed. Example: [21, 11] sorted by ones gives [21, 11] (equal digit '1'), then sorted by tens: 11 before 21 — correct. If the pass was unstable, [11, 21] might become [21, 11] again.
Q2. What is LSD vs MSD Radix Sort?concept▾
LSD (Least Significant Digit) processes digits right-to-left. Simple iterative implementation with Counting Sort. Works well for fixed-length keys. MSD (Most Significant Digit) processes digits left-to-right. Naturally recursive. More complex but can short-circuit (like Quicksort) and works for variable-length strings. MSD is used in in-place string sorting (American Flag Sort).
Q3. How is Radix Sort used in databases and distributed systems?applied▾
Database external sort: when data doesn't fit in memory, Radix Sort passes touch data sequentially — good for disk I/O. Distributed sorting: each machine handles a range of radix values in parallel (this is related to hash partitioning). GPU sorting algorithms often use Radix Sort because it maps well to parallel prefix operations (parallel scan/prefix-sum for Counting Sort).
Q4. Can Radix Sort sort strings?nonobv▾
Yes, with MSD Radix Sort. Each character is a digit, k=256 (ASCII). For variable-length strings, pad shorter strings with a sentinel character (value 0) at the end. MSD sorts character by character from left to right, recursing only on groups with equal characters at the current position. This gives O(N·L) where N is total characters and L is average length — O(N) for fixed-length strings.
Q5. Does Radix Sort work for negative numbers?applied▾
Not directly for signed integers. Common solutions: (1) Separate negatives and positives, sort each group, concatenate. (2) Offset all values by −min so they're non-negative. (3) For two's complement binary, sort all bits normally — the sign bit in two's complement can be handled with one extra pass that reverses the negative/positive ordering.
Q6. When would you choose Radix Sort over Quicksort in a competitive programming contest?deep▾
Use Radix Sort when: n ≥ 10⁶ and values are integers (e.g., 32-bit), especially when the time limit is tight and the test case might be adversarial (sorted input) for Quicksort. Radix Sort in C++ with base-256 can sort 10⁷ integers in ~0.3s vs std::sort's ~1.5s. However, Radix Sort requires O(n) extra memory — if that's unavailable, Heapsort (in-place, O(n log n) worst) is the next choice.

§5 — Common Misconceptions

Conceptual Misconceptions

❌ "Radix Sort is O(n) so it's always faster than O(n log n) sorts."

✅ Radix Sort is O(d·n) where d can be large. For 64-bit integers with base 10, d=20. Constant factors and cache effects matter. For small n, comparison sorts win.

❌ "Radix Sort can be done with any sorting algorithm per pass."

✅ The per-pass sort MUST be stable. Using an unstable sort (like Heapsort or standard Quicksort) would produce incorrect results.

❌ "MSD Radix Sort is always better than LSD because it processes the most important digits first."

✅ LSD is simpler (iterative), more cache-friendly, and sufficient for fixed-length keys. MSD is needed for variable-length strings and some in-place variants.

Implementation Misconceptions

❌ Using modulo and division naively for large bases (e.g., base 1000) — risk of integer overflow.

✅ Prefer base 256 (byte-level) or 16 (nibble-level). Extract with bitwise ops: digit = (val >> (8*pass)) & 0xFF. Faster and overflow-safe.

❌ Forgetting to copy output buffer back to input for next pass.

✅ After each Counting Sort pass, the sorted output is in a temporary buffer B. Before the next pass, copy B back to A (or ping-pong between two buffers to avoid copies).

❌ Using d = number of digits of max value but not padding shorter numbers.

✅ For LSD, shorter numbers have implicit leading zeros — extracting digit i from a number shorter than i digits correctly gives 0. No explicit padding needed in implementation.