Radix Sort

Note

This page does not cover Counting Sort.

This page briefly introduces radix sort.

Definition

Radix sort is a non-comparative sorting algorithm originally used to solve card sorting problems. Radix sort splits the elements to be sorted into \(k\) keywords and sorts each keyword sequentially to complete the sorting of all elements.

If the comparison proceeds from the 1^st keyword to the \(k\)-th keyword, it is called MSD (Most Significant Digit first) radix sort;

If the comparison proceeds from the \(k\)-th keyword to the 1^st keyword, it is called LSD (Least Significant Digit first) radix sort.

Comparison of Elements with k Keywords

Let \(a_i\) denote the \(i\)-th keyword of element \(a\).

If an element has \(k\) keywords, the default comparison method for two elements \(a\) and \(b\) is:

• Compare the 1^st keyword \(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 keyword \(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 keyword \(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 them by the units digit and pad with zeros towards higher digits. Then the \(i\)-th digit from left to right can serve as the \(i\)-th keyword;
• When comparing strings based on lexicographical order, the \(i\)-th character from left to right can serve as the \(i\)-th keyword;
• The default comparison method for C++'s std::pair and std::tuple is the same as described above.

MSD Radix Sort

Based on the comparison method for elements with \(k\) keywords, one can think: first compare the 1^st keyword of all elements to roughly determine their relative order; then for elements with the same 1^st keyword, compare their 2^nd keyword, and so on.

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

Algorithm Process

Split the elements to be sorted into \(k\) keywords. First perform a stable sort on the 1^st keyword, then for each group of elements with the same keyword, perform a stable sort on the 2^nd keyword (recursively), and so on. Finally, for each group of elements with the same keyword, perform a stable sort on the \(k\)-th keyword.

Generally, we assume radix sort is stable, so in MSD radix sort, we only consider using a stable algorithm (usually counting sort) to sort the keywords internally.

Correctness refers to the comparison of elements with \(k\) keywords above.

Reference Code

Sorting Natural Numbers

Below is C++ reference code using iterative MSD radix sort to sort elements within the unsigned int range. The values of \(W\) and \(\log_2 W\) can be adjusted (it is recommended to set \(\log_2 W\) to \(2^k\) for bitwise optimization).

Reference Code

constexpr unsigned MAXN = 1000;  // Number of elements 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-th digit
{
  return (value / powRADIX[digit]) % RADIX;
}

void MSD_radix_sort(unsigned* begin, unsigned* end, int digit)
// Indicates that the elements in [begin,end) currently have the same higher-order digits (in decimal)
// Only the last digit bits (bits 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];  // Since different recursion levels do not use cnt,tmp arrays simultaneously
                      // (each level finishes using them before calling the next level), using the static
                      // keyword can save space
  vector<unsigned> beg;
  beg.resize(RADIX + 1);  // Access to beg may conflict, use 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++)  // Counting
  {
    int bitVal = get_digit(*it, digit - 1);
    cnt[bitVal] += 1;
  }
  beg[0] = 0;  // Calculate the starting storage position (offset) for each digit value
  for (int i = 1; i <= RADIX; i++) {
    beg[i] = beg[i - 1] + cnt[i - 1];
  }
  // Calculating beg[RADIX] as well allows directly defining the range for i 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++)  // Place counting sort result into tmp
  {
    unsigned bitVal = get_digit(*it, digit - 1);  // Extract the digit-1-th bit
    tmp[beg[bitVal] + cnt[bitVal]] =
        *it;  // Because enumeration is in reverse order, this is the cnt[bitVal]+1-th element whose digit-1-th bit is 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

Below is C++ reference code using iterative MSD radix sort to sort null-terminated byte strings based on lexicographical order:

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
// Sorts strings consisting only of lowercase letters
// Parameters indicate that currently within [begin, end), elements have identical [0, digit) bits
// Now start sorting from the digit-th bit
// Example call: MSD_radix_sort_string(a, a+n, 0)
// Almost identical to the previous code, so fewer comments
// To save space and time, we sort an index array, the comparison function still compares the corresponding string bits
{
  if (begin >= end) return;
  static int tmp[MAXN + 5];
  static int cnt[28];
  vector<int> beg;
  beg.resize(28);
  // Q: Why 28?
  // A: 0=null character, 1-26=a-z, 27=extra space (to prevent 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];
  // If it's already a null character, no need to recurse, so recurse for 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)  // Call 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 \(O(n)\) linear complexity, MSD radix sort is superior to most comparison-based sorting algorithms in both time complexity and actual runtime for string sorting.

Relationship with Bucket Sort

Prerequisite: Bucket Sort

Bucket sort requires other sorting algorithms to sort the elements inside each bucket. However, it is entirely possible to perform bucket sort on each bucket recursively until the number of elements in a bucket is \(\le 1\).

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

Consequently, an optimization method for the time constant of MSD radix sort can be proposed: if at some step the number of elements in a bucket is \(\le B\) (where \(B\) is a self-chosen constant), directly perform insertion sort and return, reducing the recursion depth.

LSD Radix Sort

MSD radix sort compares from the 1^st keyword to the \(k\)-th keyword, requiring recursion or iteration, which results in a larger time constant and is somewhat inconvenient for comparing natural numbers.

Reversing the recursive operation: comparing from the \(k\)-th keyword to the 1^st keyword yields LSD (Least Significant Digit first) radix sort, a sorting algorithm that can be implemented without recursion.

Algorithm Process

Split the elements to be sorted into \(k\) keywords. First perform a stable sort on the \(k\)-th keyword for all elements, then perform a stable sort on the \((k-1)\)-th keyword for all elements, then perform a stable sort on the \((k-2)\)-th keyword for all elements, and so on. Finally, perform a stable sort on the 1^st keyword for all elements, thus completing a stable sort of the entire sequence.

LSD radix sort also requires a stable algorithm to sort the keywords internally. Similarly, counting sort is typically used.

The correctness of LSD radix sort can be referred to in Introduction to Algorithms (Third Edition), Exercise 8.3-3 Solution or explained as follows:

Correctness

Recall the comparison method for elements with \(k\) keywords:

• To determine the order of two elements \(a\) and \(b\) via \(a_1\) and \(b_1\), we need to know the conclusion from comparing \(a_2\) and \(b_2\) in advance to handle the case \(a_1 = b_1\);
• To determine the order via \(a_2\) and \(b_2\), we need to know the conclusion from comparing \(a_3\) and \(b_3\) in advance to handle the case \(a_2 = b_2\);
• ……
• To determine the order via \(a_{k-1}\) and \(b_{k-1}\), we need to know the conclusion from comparing \(a_k\) and \(b_k\) in advance 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;
• After knowing the conclusion from comparing \(a_k\) and \(b_k\), we can derive the conclusion for comparing \(a_{k-1}\) and \(b_{k-1}\);
• ……
• After knowing the conclusion from comparing \(a_2\) and \(b_2\), we can derive the conclusion for comparing \(a_1\) and \(b_1\);
• After knowing the conclusion from comparing \(a_1\) and \(b_1\), we finally derive the conclusion for comparing \(a\) and \(b\).

During this process, by comparing and rearranging the elements for each keyword, we obtain 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

Below is an implementation of LSD radix sort for sorting elements with \(k\) keywords.

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 go from n down to 1.
  // That is, when two elements have the same key value, the element originally behind should remain behind 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 key.
    counting_sort(i);
  }
}

Actually, it is not necessary to enumerate from back to front for a stable sort; performing an operation equivalent to std::exclusive_scan on the cnt array suffices.

Example Problem Luogu P1177【Template】Quick Sort

Given \(n\) positive integers, output them in ascending 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 internal sorting of keywords is stable, both MSD radix sort and LSD radix sort are stable sorting algorithms.

Time Complexity

Generally, radix sort is faster than comparison-based sorting algorithms (like quicksort). However, due to the need for additional memory space, when memory is scarce, in-place algorithms (like quicksort) might be a better choice.¹

Typically, if the value range of each keyword is not large, counting sort can be used as the internal sorting, resulting in a complexity of \(O(kn+\sum\limits_{i=1}^k w_i)\), where \(w_i\) is the size of the value range of the \(i\)-th keyword. If the keyword value range is large, one can directly use a comparison-based \(O(nk\log n)\) sort without resorting to radix sort.

Space Complexity

The space complexity of both MSD radix sort and LSD radix sort is \(O(k+n)\).

References and Notes

---

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3^rd ed.). MIT Press and McGraw-Hill, 2009. ISBN 978-0-262-03384-8. "8.3 Radix sort", pp. 199. ↩

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用