Radix Sort Explained
Radix Sort sorts integers digit by digit in O(nk) time using a stable sub-sort. Learn LSD vs MSD radix sort, how it works, and when it beats Quick Sort.
On this page +
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 nine others run step by step, with live pseudocode and comparison counters.
Launch the visualiser Software engineer at a stealth-stage startup, and previously a front-end engineer for around a year and a half.