Radix Sort non-comparison algorithm explained: digit-by-digit LSD bucket sorting, stable counting sort sub-passes, linear runtime O(d · (n + k)), and JavaScript code.
Radix Sort is a non-comparison integer sorting algorithm that avoids element comparisons by processing numbers digit by digit. In the standard Least Significant Digit (LSD) approach, it sorts elements based on the 1s place, then the 10s place, then the 100s place, and so forth until the maximum number of digits is exhausted.
For Radix Sort to work correctly, the subroutine used at each digit place must be stable (such as Counting Sort). This stability guarantees that whenever two numbers have identical digits in the current position, their relative ordering established by earlier (lower-order) passes remains intact. The algorithm runs in O(d · (n + k)) time, where d is the number of digits and k is the radix base (k = 10 for decimal).
Find the maximum value in the array to determine how many digit passes d are needed.
Start at the least significant digit place (exp = 1 for units, exp = 10 for tens, exp = 100 for hundreds).
Run a stable 10-bucket Counting Sort pass on the array, using `Math.floor(num / exp) % 10` as the extraction key.
Multiply exp by 10 (exp *= 10) and repeat the stable counting pass until exp exceeds the maximum number. The array is now fully sorted.
1function radixSort(arr) {2 if (arr.length <= 1) return arr;3 4 const max = Math.max(...arr);5 let exp = 1;6 7 // Stable counting sort subroutine for a specific digit position8 function countingSortForDigit(arr, exp) {9 const output = new Array(arr.length);10 const count = new Array(10).fill(0);11 12 // 1. Count occurrences of each digit (0-9)13 for (let i = 0; i < arr.length; i++) {14 const digit = Math.floor(arr[i] / exp) % 10;15 count[digit]++;16 }17 18 // 2. Compute cumulative prefix sums for digit positions19 for (let i = 1; i < 10; i++) {20 count[i] += count[i - 1];21 }22 23 // 3. Build output array in reverse to maintain stability24 for (let i = arr.length - 1; i >= 0; i--) {25 const digit = Math.floor(arr[i] / exp) % 10;26 output[count[digit] - 1] = arr[i];27 count[digit]--;28 }29 30 // 4. Copy sorted output back into original array31 for (let i = 0; i < arr.length; i++) {32 arr[i] = output[i];33 }34 }35 36 // Iterate through all digit places from LSD to MSD37 while (Math.floor(max / exp) > 0) {38 countingSortForDigit(arr, exp);39 exp *= 10;40 }41 42 return arr;43}44 45// Example usage:46// radixSort([170, 45, 75, 90, 802, 24, 2, 66]); // [2, 24, 45, 66, 75, 90, 170, 802]Play through every comparison, swap, and state change, adjust the speed, or enter custom inputs to test edge cases.
The full interactive roadmap is unlocking — these specialized modules land in upcoming releases.
This feature will be implemented in the next update.
This feature will be implemented in the next update.
This feature will be implemented in the next update.
Explore the full catalog — 30+ algorithms with more unlocking every release.
Ready — press Play or use step controls to walk through the algorithm.
Comparisons
0
Swaps / Shifts
0
Passes / Depth
0
Elements
10
Test your understanding of Radix Sort complexity and step mechanics.
Q1.Why must the digit-sorting subroutine in Radix Sort be stable?
Q2.What is the time complexity of LSD Radix Sort for n numbers with maximum d digits in base k?
Apply Radix Sort to real coding interview questions.
Find the maximum difference between two successive elements in its sorted form in O(n) time.