Radix Sort

Question 1

Why must the per-digit sort in Radix Sort be stable?

Accepted Answer

To preserve prior digit ordering — Stability ensures that elements sorted by earlier digits maintain their relative order when sorted by later digits.

Question 2

What is radix sort's time complexity for n keys of d digits in base b?

Accepted Answer

O(d·(n + b)) with d passes — Each of d passes runs a stable counting sort costing O(n + b), so total is O(d·(n + b)) — linear in n when d and b are bounded.

Question 3

LSD radix sort processes digits…

Accepted Answer

From least to most significant — Least-Significant-Digit radix sort sorts by the lowest digit first and the highest digit last, relying on stability of each pass.

Question 4

Each per-digit pass of radix sort MUST use a sort that is…

Accepted Answer

Stable — Stability preserves the ordering from previous (less significant) digit passes; an unstable per-digit sort would corrupt the partial order.

Question 5

Why does LSD radix sort process the LEAST significant digit first?

Accepted Answer

So the final pass yields full order — Sorting low-to-high with a stable sort means the most significant digit dominates last, while equal high digits retain the correct lower-digit order — yielding full sorted order.

Question 6

Radix sort is a comparison sort. True or false?

Accepted Answer

False, it buckets by digit — Like counting sort, radix sort distributes by digit value rather than comparing pairs, so it can beat the Ω(n log n) comparison bound.

Question 7

Choosing a LARGER base b (radix) in radix sort tends to…

Accepted Answer

Fewer passes, costlier per pass — d = log_b(maxKey), so a bigger base means fewer passes but a larger count array (O(b) per pass). Base-256 (byte-wise) is a common sweet spot.

Question 8

MSD (Most-Significant-Digit) radix sort is preferred for…

Accepted Answer

Variable-length keys/strings — MSD recurses into buckets by leading digit, matching dictionary order for strings and allowing early termination on distinguishing prefixes.

Question 9

What is radix sort's space complexity (LSD with counting-sort passes)?

Accepted Answer

O(n + b) auxiliary space per pass — Each pass needs an output buffer (O(n)) and a count array (O(b)), reused across passes: O(n + b) auxiliary space.

Question 10

For 1 million 32-bit integers, byte-wise (base-256) LSD radix sort uses how many passes?

Accepted Answer

4 passes total (32 ÷ 8) — 32-bit keys split into four 8-bit bytes ⇒ d = 4 passes, each an O(n + 256) counting sort — often faster than O(n log n) comparison sorts here.

Radix Sort

Least significant digit first

Test your knowledge

Why must the per-digit sort in Radix Sort be stable?

The short version

In more depth

LSD Radix Sort (Least Significant Digit)

Why LSD Works

When to Use

When to reach for this

Interview Questions

References & Further Reading

Love this visualization?