Radix Sort Visualization
Radix Sort organizes numbers by sorting them digit by digit. It starts with the least significant digit (rightmost) and works to the most significant digit (leftmost). Numbers are placed into buckets based on each digit's value, then collected back together in order. This process is repeated for each digit using a stable distribution — numbers with the same digit maintain their relative order from the previous pass — eventually leading to a fully sorted list.
Pseudocode
max = largest(arr)
exp = 1
while (max / exp) > 0:
buckets[0..9] = empty stacks
for i = 0 to (n - 1):
d = (arr[i] / exp) % 10
push arr[i] to buckets[d]
j = n - 1
for k = 9 to 0:
b = buckets[k]
while b is not empty:
arr[j] = b.pop()
j = j - 1
exp = exp * 10
Visualizer
Select number of elements:
Control speed:
How It Works
Radix Sort never directly compares two elements against each other. Instead, it exploits the structure of the numbers themselves. Starting from the least significant digit (ones place), the algorithm distributes all numbers into 10 buckets (0–9) based on the value of that digit. The numbers are then collected back from the buckets in order, preserving the sequence within each bucket. This process is repeated for the tens place, hundreds place, and so on, until all digit positions have been processed, resulting in a fully sorted array.
When to Use
Radix Sort excels when sorting large collections of integers or fixed-length strings where the number of digits (d) is small relative to the number of elements (n). It outperforms comparison-based sorts in these scenarios because it avoids the O(n log n) lower bound that applies to comparison sorts. However, it is less versatile — it requires elements that can be decomposed into digits or characters.
Time & Space Complexity
Metric / Operation | Complexity | Description |
|---|---|---|
| Time Complexity | O(n · d) | Where n is the number of elements and d is the number of digits in the largest number. This makes Radix Sort linear when d is a constant. |
| Space Complexity | O(n + d) | Radix Sort requires additional memory for the buckets. It is not an in-place algorithm. |
Common Interview Questions
Why is stability important for the intermediate sorting algorithm used in Radix Sort?
LSD (Least Significant Digit) Radix Sort processes digits from right to left. When sorting by a higher-order digit, equal digits rely on the preserved relative ordering established by lower-order digit passes. Instability in intermediate passes would corrupt previous digit sorting.
Can Radix Sort be used directly for floating-point numbers or negative integers?
Not directly without transformation. Negative integers require shifting numbers by adding an offset bias or separating sign bits. IEEE 754 floating-point numbers require bit-level manipulation so sign/exponent/mantissa map to monotonic unsigned integer ordering.
What is the difference between LSD and MSD Radix Sort, and when should you choose one over the other?
LSD (Least Significant Digit) sorts from right to left and requires a stable sorting algorithm across all passes. It is simpler and ideal for fixed-length keys (like integers). MSD (Most Significant Digit) sorts from left to right and recursively subdivides buckets into sub-buckets. MSD is faster for variable-length strings because it can terminate early once a prefix uniquely identifies a key.
💬 Discussion
to join the discussion
Curious to Learn More?
Hand-picked resources to deepen your understanding
© 2025 See Algorithms. Code licensed under MIT, content under CC BY-NC 4.0