Radix Sort Explained
Radix Sort sorts numbers by processing their digits one place at a time, using a stable sort (usually Counting Sort) for each digit. By avoiding comparisons entirely, it can sort large arrays of fixed-width integers in O(nk) time, where k is the number of digits — often faster than O(n log n) comparison sorts.
LSD vs MSD
There are two flavours. LSD (Least Significant Digit) radix sort starts from the rightmost digit and works left, relying on the stability of each pass to preserve earlier ordering — this is the common variant. MSD (Most Significant Digit) starts from the left and recurses, which suits variable-length strings.
How LSD Radix Sort works
For each digit position from least to most significant, perform a stable Counting Sort using that digit as the key. After processing all digit positions, the array is fully sorted. The stability of each pass is essential — it ensures that the ordering established by less significant digits survives.
When to use it
Radix Sort shines on large arrays of integers or fixed-length strings where k (digit count) is small relative to log n. For 32-bit integers, k is effectively constant, so it behaves like O(n). The cost is O(n + k) memory and the restriction to integer-like keys. See how it differs from Counting Sort in our comparison.
Frequently asked questions
What is the time complexity of Radix Sort? +
When should I use Radix Sort instead of Quick Sort? +
Is Radix Sort stable? +
See it in motion
Watch this algorithm and 9 others run step by step in our free interactive visualizer.
▶ Launch Visualiser