Skip to content

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::pair and std::tuple works 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
constexpr unsigned MAXN = 1000;  // how many numbers to sort
constexpr unsigned RADIX = 10;   // the radix
constexpr unsigned powRADIX[10] = {1,         10,        100,     1000,
                                   10000,     100000,    1000000, 10000000,
                                   100000000, 1000000000};  // powers of RADIX

unsigned get_digit(unsigned value, int digit)  // extract the digit at position digit
{
  return (value / powRADIX[digit]) % RADIX;
}

void MSD_radix_sort(unsigned* begin, unsigned* end, int digit)
// At this point the elements in [begin,end) agree (in base 10) on all leading digits;
// only the last `digit` digits (positions digit-1 down to 0) still need sorting
// Example call: MSD_radix_sort(a,a+n,10)
{
  if (begin >= end)  // empty range
  {
    return;
  }
  /**Counting sort (one personal way to write it, for reference only)**/
  static unsigned cnt[RADIX + 1],
      tmp[MAXN + 5];  // Different recursion levels never use the cnt and tmp arrays
                      // at the same time (a level is done with them before it calls
                      // the next), so the static keyword saves space
  vector<unsigned> beg;
  beg.resize(RADIX + 1);  // accesses to beg could conflict, so use a local variable
  for (int i = 0; i <= RADIX; i++) {
    cnt[i] = beg[i] = 0;  // clearing is a good habit
  }
  for (unsigned* it = begin; it != end; it++)  // count
  {
    int bitVal = get_digit(*it, digit - 1);
    cnt[bitVal] += 1;
  }
  beg[0] = 0;  // compute where each digit value starts to be stored (its offset)
  for (int i = 1; i <= RADIX; i++) {
    beg[i] = beg[i - 1] + cnt[i - 1];
  }
  // beg[RADIX] is computed too, so that the range for i is simply [beg[i],beg[i+1])
  // with no need to worry about beg[i+1] going out of bounds
  for (int i = 0; i < RADIX; i++) {
    cnt[i] = 0;
  }
  for (unsigned* it = begin; it != end; it++)  // put the counting sort result into tmp
  {
    unsigned bitVal = get_digit(*it, digit - 1);  // extract the digit at position digit - 1
    // Scanning in the original order, this is element number cnt[bitVal]+1 whose digit at position digit-1 is bitVal
    tmp[beg[bitVal] + cnt[bitVal]] = *it;
    cnt[bitVal]++;
  }
  for (unsigned* it = begin; it != end; it++)  // copy tmp back into the original array
  {
    *it = tmp[it - begin];
  }
  /**Recursively sort each bucket by the next digit**/
  if (digit == 1)  // already at the lowest digit
  {
    return;
  }
  for (int i = 0; i < RADIX; i++)  // recursively sort by the next digit
  {
    MSD_radix_sort(begin + beg[i], begin + beg[i + 1], digit - 1);
  }
}

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
constexpr int MAXN = 1000;

int get_digit(string* arr, int i, int dig) {
  if (arr[i][dig] == '\0') return 0;
  return arr[i][dig] - 'a' + 1;
}

void MSD_radix_sort_string_base(string* arr, int* begin, int* end,
                                int digit)  // the main routine
// Sorts strings consisting only of lowercase letters
// The arguments mean that the elements in [begin,end) now agree on positions [0,digit)
// and that sorting now starts at position digit
// Example call: MSD_radix_sort_string(a, a + n)
// Almost identical to the previous code, so there are fewer comments
// To save space and time we sort an array of indices; comparisons still look at the corresponding position of the strings
{
  if (begin >= end) return;
  static int tmp[MAXN + 5];
  static int cnt[28];
  vector<int> beg;
  beg.resize(28);
  // Q: Why size 28?
  // A: 0 = null character, 1-26 = a-z, 27 = extra slot (to avoid going out of bounds)
  for (int i = 0; i < 28; i++) cnt[i] = beg[i] = 0;
  for (int* it = begin; it != end; it++) cnt[get_digit(arr, *it, digit)] += 1;
  beg[0] = 0;
  for (int i = 1; i <= 27; i++) beg[i] = beg[i - 1] + cnt[i - 1];
  for (int i = 0; i < 28; i++) cnt[i] = 0;
  for (int* it = begin; it != end; it++) {
    int bitVal = get_digit(arr, *it, digit);
    tmp[beg[bitVal] + cnt[bitVal]] = *it;
    cnt[bitVal]++;
  }
  for (int* it = begin; it != end; it++) *it = tmp[it - begin];
  // Once we are at the null character there is no need to recurse, so recurse on 1~26
  for (int i = 1; i <= 26; i++)
    MSD_radix_sort_string_base(arr, begin + beg[i], begin + beg[i + 1],
                               digit + 1);
}

int label[MAXN + 5];

void MSD_radix_sort_string(string* begin, string* end)  // the interface to call
{
  static string tmp[MAXN + 5];
  int n = end - begin;
  for (int i = 0; i < n; i++) {
    label[i] = i;
    tmp[i] = *(begin + i);
  }
  MSD_radix_sort_string_base(tmp, label, label + n, 0);
  for (int i = 0; i < n; i++) {
    *(begin + i) = tmp[label[i]];
  }
}

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.

A complete run of LSD radix sort on an example

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

\[ \begin{array}{ll} 1 & \textbf{Input. } \text{An array } A \text{ consisting of }n\text{ elements, where each element has }k\text{ keys.}\\ 2 & \textbf{Output. } \text{Array }A\text{ will be sorted in nondecreasing order stably.} \\ 3 & \textbf{Method. } \\ 4 & \textbf{for }i\gets k\textbf{ down to }1\\ 5 & \qquad\text{sort }A\text{ into nondecreasing order by the }i\text{-th key stably} \end{array} \]

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
constexpr int N = 100010;
constexpr int W = 100010;
constexpr int K = 100;

int n, w, k, cnt[W];

struct Element {
  int key[K];
} a[N], b[N];

void counting_sort(int p) {
  memset(cnt, 0, sizeof(cnt));
  for (int i = 1; i <= n; ++i) ++cnt[a[i].key[p]];
  for (int i = 1; i <= w; ++i) cnt[i] += cnt[i - 1];
  // To keep the sort stable, i must run from n down to 1 in this loop:
  // of two elements with equal keys, the one that came later must still come later after sorting
  for (int i = n; i >= 1; --i) b[cnt[a[i].key[p]]--] = a[i];
  memcpy(a, b, sizeof(a));
}

void radix_sort() {
  for (int i = k; i >= 1; --i) {
    // sort by this key using counting sort
    counting_sort(i);
  }
}

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
#include <algorithm>
#include <iostream>
#include <utility>

void radix_sort(int n, int a[]) {
  int *b = new int[n];  // temporary space
  int *cnt = new int[1 << 8];
  int mask = (1 << 8) - 1;
  int *x = a, *y = b;
  for (int i = 0; i < 32; i += 8) {
    for (int j = 0; j != (1 << 8); ++j) cnt[j] = 0;
    for (int j = 0; j != n; ++j) ++cnt[x[j] >> i & mask];
    for (int sum = 0, j = 0; j != (1 << 8); ++j) {
      // equivalent to std::exclusive_scan(cnt, cnt + (1 << 8), cnt, 0);
      sum += cnt[j], cnt[j] = sum - cnt[j];
    }
    for (int j = 0; j != n; ++j) y[cnt[x[j] >> i & mask]++] = x[j];
    std::swap(x, y);
  }
  delete[] cnt;
  delete[] b;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n;
  std::cin >> n;
  int *a = new int[n];
  for (int i = 0; i < n; ++i) std::cin >> a[i];
  radix_sort(n, a);
  for (int i = 0; i < n; ++i) std::cout << a[i] << " \n"[i == n - 1];
  delete[] a;
  return 0;
}

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,

\[ O\left(kn+\sum_{i=1}^k w_i\right),\qquad O\left(kn+\sum_{i=1}^k b_iw_i\right), \]

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


  1. 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. ↩