Radix Sort (LSD)

Sort one digit at a time, right-to-left, using stable counting sort per pass.

Best: O(d·(n+k)) Worst: O(d·(n+k)) Space: O(n+k) Stable
slow fast
Scanning
Bucketing
Placed
Pass done
Step
0/0
Pass
0
Digit
ones
Total work
0

Algorithm Trace

Press Start to run animation. LSD Radix Sort processes the rightmost digit first.

LSD Radix Sort: O(d·(n+k)) time, O(n+k) space, stable. Used inside CUB GPU sort, ClickHouse, and TeraSort. Beats Tim/Quick sort for large fixed-width integer arrays.