codaBack to Academy
sorting
Radix Sort
Radix Sort is a non-comparison-based algorithm that sorts integers by processing individual digits from the least significant to the most significant, using a stable sort (typically counting sort) as a subroutine at each digit position. It achieves linear time complexity relative to the number of elements and the number of digits, outperforming comparison-based sorts when the number of digits is constant.
Use Cases
- •Sorting large sets of integers or fixed-length strings
- •When the number of digits (d) is small relative to the dataset size
- •Replacing comparison sorts when data fits the fixed-width integer model
Complexity Analysis
| Metric | Best | Average | Worst |
|---|---|---|---|
| Time | O(d × n) | O(d × n) | O(d × n) |
| Space | O(n + k) | ||
Visualization
64
34
25
12
22
11
90
Implementation
Output
Click "Run Code" to see output...