What is Radix Sort?
Learn how radix sort processes digits with a stable counting sort to achieve linear time for fixed-width integer keys.
Expected Interview Answer
Radix sort sorts integers (or fixed-length strings) by repeatedly applying a stable sort, usually counting sort, on one digit position at a time, moving from the least significant digit to the most significant, achieving O(d * (n + k)) time where d is the number of digits and k is the digit base.
Because it processes digits from least significant to most significant, radix sort relies on the stability of the underlying per-digit sort to preserve the ordering established by earlier, less significant passes — get a non-stable digit sort involved and the whole algorithm breaks. Each digit pass costs O(n + k) using counting sort with base k (commonly 10 or 256), and with d digits total the overall cost is O(d * (n + k)), which is linear when d and k are both small relative to n. This lets radix sort beat the O(n log n) comparison-sort bound for fixed-width keys like 32-bit integers, phone numbers, or zero-padded IDs. Its main costs are the extra O(n + k) space for the digit-pass buffers and the requirement that keys have a bounded, known digit width, which makes it a poor fit for arbitrary variable-length or floating-point data without extra preprocessing.
- Linear O(d * (n + k)) time for fixed-width keys
- Beats the comparison-sort O(n log n) lower bound
- Naturally stable when built on a stable digit-pass sort
- Well suited to integers, dates, and fixed-length strings
AI Mentor Explanation
A tournament organizer sorting four-digit player ID badges processes one digit column at a time, starting with the rightmost (ones) column and using a stable bucket pass to group badges by that single digit while preserving their current relative order. Moving one column left to the tens digit and repeating the same stable bucketing, badges that already match on the ones digit stay in the order the previous pass established. By the time the thousands digit pass finishes, the badges are fully sorted, because each pass only had to be correct about one column while trusting the stability of every prior pass. This column-by-column approach avoids ever comparing two full four-digit numbers directly.
Step-by-Step Explanation
Step 1
Determine the max digit count d
Find the widest key in the dataset to know how many digit passes are needed.
Step 2
Sort by the least significant digit
Run a stable counting sort keyed on the rightmost digit first.
Step 3
Move left one digit at a time
Repeat the stable per-digit sort for each subsequent, more significant digit position.
Step 4
Finish after the most significant digit
After d passes the array is fully sorted; correctness depends on every pass being stable.
What Interviewer Expects
- Explain the least-significant-digit ordering and why stability across passes is mandatory
- State O(d * (n + k)) time complexity and connect it to counting sort as the subroutine
- Identify that it works for fixed-width integers or fixed-length strings, not arbitrary data
- Compare against comparison sorts, noting it can beat O(n log n) for bounded-width keys
Common Mistakes
- Sorting most-significant-digit first without extra care, which does not work with a naive single stable pass per digit
- Using a non-stable sort for the digit passes, which breaks the final ordering
- Applying radix sort to floating-point or variable-length data without proper key normalization
- Forgetting the extra O(n + k) space needed by each counting-sort pass
Best Answer (HR Friendly)
“Radix sort sorts numbers one digit at a time, starting from the rightmost digit, using a sort that keeps ties in order at each step. By the time it works through every digit position, the whole thing ends up fully sorted, and because each pass is cheap and linear, the total time stays linear too. I would reach for it with fixed-width integers or IDs where I want to avoid the log n factor of a comparison sort.”
Code Example
def counting_sort_by_digit(arr, exp):
n = len(arr)
output = [0] * n
counts = [0] * 10
for value in arr:
digit = (value // exp) % 10
counts[digit] += 1
for i in range(1, 10):
counts[i] += counts[i - 1]
for value in reversed(arr):
digit = (value // exp) % 10
counts[digit] -= 1
output[counts[digit]] = value
return output
def radix_sort(arr):
if not arr:
return arr
max_value = max(arr)
exp = 1
while max_value // exp > 0:
arr = counting_sort_by_digit(arr, exp)
exp *= 10
return arrFollow-up Questions
- Why must each digit pass in radix sort be stable?
- How would you extend radix sort to handle negative integers?
- When does radix sort outperform a comparison sort like quicksort in practice?
- How would you adapt radix sort to sort fixed-length strings instead of numbers?
MCQ Practice
1. What is the overall time complexity of radix sort with d digits, n elements, and base k?
Each of the d digit passes costs O(n + k) using a stable counting sort, giving O(d * (n + k)) total.
2. Why must radix sort process digits from least significant to most significant using a stable sort?
Later passes on more significant digits must not disturb the relative order already fixed by earlier passes, which only holds if every pass is stable.
3. Radix sort is best suited for which type of data?
Radix sort needs a bounded, known number of digit positions, making it a natural fit for fixed-width integers and fixed-length strings.
Flash Cards
What subroutine does radix sort typically use per digit? — A stable counting sort, applied to one digit position at a time.
What is radix sort’s time complexity? — O(d * (n + k)), where d is digit count and k is the digit base.
Why must the per-digit sort be stable? — So the ordering established by earlier, less significant digit passes is preserved through later passes.
What kind of data is radix sort best suited for? — Fixed-width integers or fixed-length strings with a bounded number of digit positions.