Radix Sort
Note
This page is not about counting sort.
This page gives a brief introduction to radix sort.
Definition
Radix sort is a non-comparative sorting algorithm, first used for sorting cards. It splits each element to be sorted into \(k\) keys and sorts by the keys one at a time; once every key has been handled, the elements are sorted.
If the keys are compared in order from key \(1\) to key \(k\), the algorithm is called MSD (most significant digit first) radix sort.
If they are compared in order from key \(k\) to key \(1\), it is called LSD (least significant digit first) radix sort.
Comparing k-key elements
Below, \(a_i\) denotes key \(i\) of an element \(a\).
Suppose elements have \(k\) keys. By default, two elements \(a\) and \(b\) are compared as follows:
- Compare key \(1\) of the two elements, \(a_1\) and \(b_1\). If \(a_1 < b_1\) then \(a < b\); if \(a_1 > b_1\) then \(a > b\); if \(a_1 = b_1\), go on to the next step.
- Compare key \(2\) of the two elements, \(a_2\) and \(b_2\). If \(a_2 < b_2\) then \(a < b\); if \(a_2 > b_2\) then \(a > b\); if \(a_2 = b_2\), go on to the next step.
- ...
- Compare key \(k\) of the two elements, \(a_k\) and \(b_k\). If \(a_k < b_k\) then \(a < b\); if \(a_k > b_k\) then \(a > b\); if \(a_k = b_k\) then \(a = b\).
Examples:
- To compare natural numbers, align them at the ones digit and pad the high-order end with \(0\). The \(i\)-th digit of a number, counting from the left, then serves as key \(i\).
- To compare strings in lexicographical order, the \(i\)-th character of a string, counting from the left, serves as key \(i\).
- The default comparison of C++'s built-in
std::pairandstd::tupleworks in the same way.
MSD radix sort
The way k-key elements are compared suggests a method: first compare all elements by key \(1\), which settles their rough order; then, among elements with the same key \(1\), compare by key \(2\); and so on.
Because the keys are compared in order from key \(1\) to key \(k\), the sorting algorithm that comes out of this idea is called MSD (most significant digit first) radix sort.
Procedure
Split each element to be sorted into \(k\) keys. First sort stably by key \(1\). Then, within each group of elements with the same key, sort stably by key \(2\) (recursively), and so on, until finally each group of elements with the same key is sorted stably by key \(k\).
Radix sort is normally taken to be stable, so in MSD radix sort too we only consider using a stable algorithm (usually counting sort) for the inner sort on each key.
For correctness, see the comparison of k-key elements above.
Reference code
Sorting natural numbers
Below is a recursive MSD radix sort that handles at most MAXN integers in \([0,2^{32}-1]\). The initial call uses digit=10. To change the radix, update RADIX and powRADIX together.
Reference code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 | |
Sorting strings
Below is a recursive MSD radix sort that puts std::string values consisting only of lowercase English letters into lexicographical order:
Reference code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | |
Comparing two strings can easily cost linear time, \(O(n)\), so for sorting strings MSD radix sort beats most comparison-based sorting algorithms both in time complexity and in actual running time.
Relation to bucket sort
Prerequisites: bucket sort
Bucket sort relies on some other sorting algorithm to sort the elements inside each bucket. But nothing stops us from running bucket sort again on every bucket, until at some step a bucket holds \(\le 1\) elements.
So another way to understand MSD radix sort is as bucket sort implemented with bucket sort.
This also suggests a way to improve the constant factor of MSD radix sort: once a bucket holds \(\le B\) elements at some step (\(B\) is a constant of your choosing), run insertion sort on it and return. This reduces the number of recursive calls.
LSD radix sort
MSD radix sort compares the keys in order from key \(1\) to key \(k\), which takes recursion or iteration to implement. Its constant factor is still fairly large, and it is somewhat awkward for comparing natural numbers.
Turning the recursion around, that is, comparing in order from key \(k\) to key \(1\), gives LSD (least significant digit first) radix sort, a sorting algorithm that needs no recursion.
Procedure
Split each element to be sorted into \(k\) keys. First sort all elements stably by key \(k\), then sort all elements stably by key \(k-1\), then sort all elements stably by key \(k-2\), and so on, until finally all elements are sorted stably by key \(1\). The whole sequence is now stably sorted.
LSD radix sort also needs a stable algorithm for the inner sort on each key. Here too, counting sort is the usual choice.
For the correctness of LSD radix sort, see the solution to Exercise 8.3-3 of Introduction to Algorithms (3rd edition), or the explanation below:
Correctness
Recall how k-key elements are compared:
- To decide the order of two elements \(a\) and \(b\) from \(a_1\) and \(b_1\) alone, we need to know in advance the outcome of comparing \(a_2\) and \(b_2\), so that we can handle the case \(a_1 = b_1\).
- To decide the order of \(a\) and \(b\) from \(a_2\) and \(b_2\) alone, we need to know in advance the outcome of comparing \(a_3\) and \(b_3\), so that we can handle the case \(a_2 = b_2\).
- ...
- To decide the order of \(a\) and \(b\) from \(a_{k-1}\) and \(b_{k-1}\) alone, we need to know in advance the outcome of comparing \(a_k\) and \(b_k\), so that we can handle the case \(a_{k-1} = b_{k-1}\).
- \(a_k\) and \(b_k\) can be compared directly.
Now reverse the order:
- \(a_k\) and \(b_k\) can be compared directly.
- Once we know the outcome of comparing \(a_k\) and \(b_k\), we get the outcome of comparing \(a_{k-1}\) and \(b_{k-1}\).
- ...
- Once we know the outcome of comparing \(a_2\) and \(b_2\), we get the outcome of comparing \(a_1\) and \(b_1\).
- Once we know the outcome of comparing \(a_1\) and \(b_1\), we finally get the outcome of comparing \(a\) and \(b\).
Rearranging the elements as we go, while comparing on each key in turn, gives LSD radix sort.
Pseudocode
Reference code
The code below sorts k-key elements with LSD radix sort.
Reference code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | |
In fact, the sort does not have to iterate over the elements from back to front to be stable: it is enough to apply to the cnt array an operation equivalent to std::exclusive_scan.
Example: Luogu P1177 [Template] Sorting
Given \(n\) positive integers, print them in increasing order.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | |
Properties
Stability
If the inner sort on each key is stable, then MSD radix sort and LSD radix sort are both stable sorting algorithms.
Time complexity
Radix sort is generally faster than comparison-based sorting algorithms such as quicksort. But it needs extra memory, so when memory is scarce an in-place algorithm such as quicksort may be the better choice.1
The time bounds below assume that extracting a single key and moving one element (or its index) each take \(O(1)\) time. In general, if the value range of every key is small, counting sort can serve as the inner sort, and LSD and MSD then run in, respectively,
where \(b_i\) is the number of buckets on which counting sort is actually run at level \(i\), and \(w_i\) is the size of the value range of key \(i\). If the value ranges of the keys are large, simply use an \(O(nk\log n)\) comparison-based sort; there is no need for radix sort.
Space complexity
Here we consider the auxiliary space used beyond the input, assuming that each element or its index occupies \(O(1)\) space. With counting sort, LSD can reuse one temporary array of length \(n\) and one counting array, for \(O(n+\max_i w_i)\) auxiliary space. A recursive MSD that reuses the temporary array but keeps the bucket boundaries at every level of the recursion uses \(O(n+\sum_{i=1}^k w_i)\) auxiliary space. When the size of the value range of each digit is fixed, these simplify to \(O(n)\) and \(O(n+k)\) respectively. Here \(k\) is the number of keys.
References and notes
-
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill, 2009. ISBN 978-0-262-03384-8. "8.3 Radix sort", pp. 199. ↩
This page is an unofficial English translation of the original OI Wiki page (revision b469442a), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: partychicken, 24OI-bot, ouuan, H-J-Granger, Early0v0, NachtgeistW, sbofgayschool, Konano, Enter-tainer, Alisahhh, ksyx, hly1204, Ir1d, iamtwz, untitledunrevised, Tiphereth-A, OhGaGaGaGa, TrickEye, smkttl, c-forrest, TH911 (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.