AIOJ

Reminder

This page introduces something other than counting sort.

This page briefly introduces radix sort.

Definition

Radix sort (English: Radix sort) is a non-comparison sorting algorithm, originally used to solve the problem of sorting cards. Radix sort divides the elements to be sorted into $k$ keys, sorts the keys one by one, and then completes the sorting of all elements.

If the keys are compared in order from the $1$ -st key to the $k$ -th key, the radix sort is called MSD (Most Significant Digit first) radix sort;

If the keys are compared in order from the $k$ -th key to the $1$ -st key, the radix sort is called LSD (Least Significant Digit first) radix sort.

Comparison of k-Key Elements

Let $a_i$ denote the $i$ -th key of element $a$ .

Suppose an element has $k$ keys. For two elements $a$ and $b$ , the default comparison method is:

Compare the $1$ -st keys $a_1$ and $b_1$ of the two elements. If $a_1 < b_1$ , then $a < b$ ; if $a_1 > b_1$ , then $a > b$ ; if $a_1 = b_1$ , proceed to the next step;
Compare the $2$ -nd keys $a_2$ and $b_2$ of the two elements. If $a_2 < b_2$ , then $a < b$ ; if $a_2 > b_2$ , then $a > b$ ; if $a_2 = b_2$ , proceed to the next step;
…
Compare the $k$ -th keys $a_k$ and $b_k$ of the two elements. 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:

When comparing natural numbers, align the natural numbers by their units digits and pad the higher positions with $0$ . The $i$ -th digit from the left of a number can then serve as the $i$ -th key;
When comparing strings lexicographically, the $i$ -th character from the left of a string can serve as the $i$ -th key;
The default comparison methods of C++'s std::pair and std::tuple are the same as the above.

MSD Radix Sort

Based on the comparison method for k-key elements, we can imagine first comparing the $1$ -st key of all elements to determine their approximate relative order; then, for elements with the same $1$ -st key, comparing their $2$ -nd keys, and so on.

Since the comparison proceeds from the $1$ -st key to the $k$ -th key, the sorting algorithm derived from the above idea is called MSD (Most Significant Digit first) radix sort.

Algorithm

Divide the elements to be sorted into $k$ keys. First perform a stable sort on the $1$ -st key. Then, for each group of elements with the same key, perform a stable sort on the $2$ -nd key (recursively). Finally, for each group of elements with the same key, perform a stable sort on the $k$ -th key.

Generally speaking, we assume radix sort to be stable, so in MSD radix sort we consider using only stable algorithms (usually counting sort) to sort the keys in the inner layer.

For correctness, see the comparison of k-key elements above.

Reference Code

Sorting Natural Numbers

The following is reference C++ code that uses iterative MSD radix sort to sort elements in the range of unsigned int. The values of $W$ and $\log_2 W$ can be adjusted (it is recommended to set $\log_2 W$ to $2^k$ to optimize bit operations).

Reference Code

constexpr unsigned MAXN = 1000;  // number of numbers to sort
constexpr unsigned RADIX = 10;   // 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)
// indicates that the first several digits (in base 10) of the elements in [begin,end) are the same
// only the last digit positions (from digit-1 to 0) need to be sorted
// example call: MSD_radix_sort(a,a+n,9)
{
  if (begin >= end)  // empty interval
  {
    return;
  }
  /** Counting sort (personal implementation for reference only) **/
  static unsigned cnt[RADIX + 1],
      tmp[MAXN + 5];  // cnt and tmp are not used simultaneously by different recursion levels
                      // each level is finished before the next level is called, so the static
                      // keyword saves space
  vector<unsigned> beg;
  beg.resize(RADIX + 1);  // access to beg may 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;  // calculate the starting position (offset) for storing each digit
  for (int i = 1; i <= RADIX; i++) {
    beg[i] = beg[i - 1] + cnt[i - 1];
  }
  // beg[RADIX] is computed as well so that the range for i can be directly defined as [beg[i],beg[i+1])
  // without worrying 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 bit-1
    tmp[beg[bitVal] + cnt[bitVal]] =
        *it;  // because the enumeration is in reverse order, this is the cnt[bitVal]+1-th element whose bit-1 is
              // cnt[bitVal]
    cnt[bitVal]++;
  }
  for (unsigned* it = begin; it != end; it++)  // copy tmp back to the original array
  {
    *it = tmp[it - begin];
  }
  /** Iterative computation **/
  if (digit == 1)  // already at the lowest digit
  {
    return;
  }
  for (int i = 0; i < RADIX; i++)  // recursively sort the next digit
  {
    MSD_radix_sort(begin + beg[i], begin + beg[i + 1], digit - 1);
  }
}

Sorting Strings

The following is reference C++ code that uses iterative MSD radix sort to sort null-terminated byte strings lexicographically:

Reference Code

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)  // main function
// sort strings consisting only of lowercase letters
// the parameters indicate that bits [0,digit) of the elements in [begin,end) are the same
// sorting now starts from bit digit
// example call: MSD_radix_sort_string(a,a+n,0)
// almost exactly the same as the previous code, so there are fewer comments
// to save space and time, sort the index array; the comparison function still compares the corresponding positions of the strings
{
  if (begin >= end) return;
  static int tmp[MAXN + 5];
  static int cnt[28];
  vector<int> beg;
  beg.resize(28);
  // Q: Why 28?
  // A: 0=empty character, 1-26=a-z, 27=extra space (to prevent out-of-bounds access)
  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];
  // if it is already an empty character, recursion is unnecessary, so recurse over 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)  // interface
{
  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]];
  }
}

Since comparing two strings can easily reach a linear complexity of $O(n)$ , for string sorting, MSD radix sort is more efficient than most comparison-based sorting algorithms both in time complexity and actual runtime.

Relationship with Bucket Sort

Prerequisite knowledge: Bucket sort

Bucket sort needs another sorting algorithm to sort the elements inside each bucket. In fact, bucket sort can be applied to each bucket recursively until the number of elements in a bucket is $\le 1$ .

Therefore, another way to understand MSD radix sort is as bucket sort implemented using bucket sort.

Accordingly, an optimization method for the time constant of MSD radix sort can be proposed: if the number of elements in a bucket is $\le B$ at some step ( $B$ is a constant chosen by the user), directly perform insertion sort and return to reduce the number of recursive calls.

LSD Radix Sort

MSD radix sort compares keys in order from the $1$ -st key to the $k$ -th key. It therefore requires recursion or iteration, and its time constant is still relatively large; it is also somewhat inconvenient for comparing natural numbers.

If the recursive operation is reversed—comparing keys in order from the $k$ -th key to the $1$ -st key—we obtain LSD (Least Significant Digit first) radix sort, a sorting algorithm that can be completed without recursion.

Algorithm

Divide the elements to be sorted into $k$ keys. First perform a stable sort on the $k$ -th key of all elements, then on the $k-1$ -st key of all elements, then on the $k-2$ -nd key of all elements, and so on. Finally perform a stable sort on the $1$ -st key of all elements, completing a stable sort of the entire sequence.

An example of the complete process of LSD radix sort

LSD radix sort also needs a stable algorithm to sort the keys in the inner layer. Similarly, counting sort is usually used.

For the correctness of LSD radix sort, see the solution to exercise 8.3-3 in Introduction to Algorithms (third edition) or the explanation below:

Correctness

Recall the comparison method for k-key elements:

To determine the ordering of two elements $a$ and $b$ using only $a_1$ and $b_1$ , we need to know in advance the conclusion obtained by comparing $a_2$ and $b_2$ to handle the case $a_1 = b_1$ ;
To determine the ordering of two elements $a$ and $b$ using only $a_2$ and $b_2$ , we need to know in advance the conclusion obtained by comparing $a_3$ and $b_3$ to handle the case $a_2 = b_2$ ;
……
To determine the ordering of two elements $a$ and $b$ using only $a_{k-1}$ and $b_{k-1}$ , we need to know in advance the conclusion obtained by comparing $a_k$ and $b_k$ to 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 the conclusion obtained by comparing $a_k$ and $b_k$ is known, the conclusion for comparing $a_{k-1}$ and $b_{k-1}$ can be obtained;
……
Once the conclusion obtained by comparing $a_2$ and $b_2$ is known, the conclusion for comparing $a_1$ and $b_1$ can be obtained;
Once the conclusion obtained by comparing $a_1$ and $b_1$ is known, the conclusion for comparing $a$ and $b$ is finally obtained.

During this process, rearranging the elements while comparing each key yields 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 following sorts k-key elements using LSD radix sort.

Reference Code

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 ensure sorting stability, the loop variable i should run from n down to 1
  // That is, when two elements have the same key value, the element originally later should still be 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) {
    // Use counting sort to sort the keys
    counting_sort(i);
  }
}

It is not actually necessary to enumerate from back to front for the sort to be stable; it is enough to perform an operation on the cnt array equivalent to std::exclusive_scan.

Example: Luogu P1177 [Template] Sorting

Given $n$ positive integers, output them in increasing order.

#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] << ' ';
  delete[] a;
  return 0;
}

Properties

Stability

If the inner-key sorting is stable, both MSD radix sort and LSD radix sort are stable sorting algorithms.

Time complexity

Generally speaking, radix sort is faster than comparison-based sorting algorithms (such as quicksort). However, because it requires additional memory space, when memory is scarce, an in-place algorithm (such as quicksort) may be a better choice.¹

In general, if the value range of each key is not large, counting sort can be used as the inner sort. Its complexity is $O(kn+\sum\limits_{i=1}^k w_i)$ , where $w_i$ is the size of the value range of the $i$ -th key. If the key value range is very large, one can directly use a comparison-based $O(nk\log n)$ sort without radix sort.

Space Complexity

The space complexities of both MSD radix sort and LSD radix sort are $O(k+n)$ .

References and notes

Footnotes

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