Radix Sort
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]
k = n - 1
for j = 9 to 0:
b = buckets[j]
while b is not empty:
arr[k] = b.pop()
k = k - 1
exp = exp * 10
Visualizer
Select number of elements:
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 (k) 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. For floating-point numbers or complex objects, comparison-based algorithms are more appropriate.
Time & Space Complexity
Metric / Operation | Complexity | Description |
|---|---|---|
| Time Complexity | O(n × k) | Where n is the number of elements and k is the number of digits in the largest number. This makes Radix Sort linear when k is a constant. |
| Space Complexity | O(n + k) | Radix Sort requires additional memory for the buckets. It is not an in-place algorithm. |
💬 Discussion
Sign in 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.