11.10 Radix Sort¶
The previous section introduced counting sort, which is suitable when the number of items \(n\) is large but the value range \(m\) is small. Suppose we need to sort \(n = 10^6\) student IDs, each of which is an 8-digit number. Then the value range \(m = 10^8\) is very large. Using counting sort would require a large amount of memory, whereas radix sort avoids this problem.
Radix sort is based on the same core idea as counting sort: it also sorts by counting occurrences. Building on this, radix sort exploits the positional relationship among digits and sorts them one digit at a time to obtain the final result.
11.10.1 Algorithm Flow¶
Taking student ID data as an example, assume the lowest digit is the \(1\)st digit and the highest digit is the \(8\)th digit. The flow of radix sort is shown in Figure 11-18.
- Initialize the digit \(k = 1\).
- Perform "counting sort" on the \(k\)th digit of the student IDs. After completion, the data will be sorted from smallest to largest according to the \(k\)th digit.
- Increase \(k\) by \(1\), then return to step
2.and continue iterating until all digits are sorted, at which point the process ends.
Figure 11-18 Radix sort algorithm flow
Next, let us look at the code. For a number \(x\) in base \(d\), its \(k\)th digit \(x_k\) can be obtained with the following formula:
\[
x_k = \lfloor\frac{x}{d^{k-1}}\rfloor \bmod d
\]
Here, \(\lfloor a \rfloor\) denotes rounding the floating-point number \(a\) down, and \(\bmod \: d\) denotes taking the remainder modulo \(d\). For student ID data, \(d = 10\) and \(k \in [1, 8]\).
Additionally, we need to slightly modify the counting sort code to make it sort based on the \(k\)th digit of the number:
radix_sort.py
def digit(num: int, exp: int) -> int:
"""Get the k-th digit of element num, where exp = 10^(k-1)"""
# Passing exp instead of k can avoid repeated expensive exponentiation here
return (num // exp) % 10
def counting_sort_digit(nums: list[int], exp: int):
"""Counting sort (based on nums k-th digit)"""
# Decimal digit range is 0~9, therefore need a bucket array of length 10
counter = [0] * 10
n = len(nums)
# Count the occurrence of digits 0~9
for i in range(n):
d = digit(nums[i], exp) # Get the k-th digit of nums[i], noted as d
counter[d] += 1 # Count the occurrence of digit d
# Calculate prefix sum, converting "occurrence count" into "array index"
for i in range(1, 10):
counter[i] += counter[i - 1]
# Traverse in reverse, based on bucket statistics, place each element into res
res = [0] * n
for i in range(n - 1, -1, -1):
d = digit(nums[i], exp)
j = counter[d] - 1 # Get the index j for d in the array
res[j] = nums[i] # Place the current element at index j
counter[d] -= 1 # Decrease the count of d by 1
# Use result to overwrite the original array nums
for i in range(n):
nums[i] = res[i]
def radix_sort(nums: list[int]):
"""Radix sort"""
# Get the maximum element of the array, used to determine the maximum number of digits
m = max(nums)
# Traverse from the lowest to the highest digit
exp = 1
while exp <= m:
# Perform counting sort on the k-th digit of array elements
# k = 1 -> exp = 1
# k = 2 -> exp = 10
# i.e., exp = 10^(k-1)
counting_sort_digit(nums, exp)
exp *= 10
radix_sort.cpp
/* Get the k-th digit of element num, where exp = 10^(k-1) */
int digit(int num, int exp) {
// Passing exp instead of k can avoid repeated expensive exponentiation here
return (num / exp) % 10;
}
/* Counting sort (based on nums k-th digit) */
void countingSortDigit(vector<int> &nums, int exp) {
// Decimal digit range is 0~9, therefore need a bucket array of length 10
vector<int> counter(10, 0);
int n = nums.size();
// Count the occurrence of digits 0~9
for (int i = 0; i < n; i++) {
int d = digit(nums[i], exp); // Get the k-th digit of nums[i], noted as d
counter[d]++; // Count the occurrence of digit d
}
// Calculate prefix sum, converting "occurrence count" into "array index"
for (int i = 1; i < 10; i++) {
counter[i] += counter[i - 1];
}
// Traverse in reverse, based on bucket statistics, place each element into res
vector<int> res(n, 0);
for (int i = n - 1; i >= 0; i--) {
int d = digit(nums[i], exp);
int j = counter[d] - 1; // Get the index j for d in the array
res[j] = nums[i]; // Place the current element at index j
counter[d]--; // Decrease the count of d by 1
}
// Use result to overwrite the original array nums
for (int i = 0; i < n; i++)
nums[i] = res[i];
}
/* Radix sort */
void radixSort(vector<int> &nums) {
// Get the maximum element of the array, used to determine the maximum number of digits
int m = *max_element(nums.begin(), nums.end());
// Traverse from the lowest to the highest digit
for (int exp = 1; exp <= m; exp *= 10)
// Perform counting sort on the k-th digit of array elements
// k = 1 -> exp = 1
// k = 2 -> exp = 10
// i.e., exp = 10^(k-1)
countingSortDigit(nums, exp);
}
radix_sort.java
/* Get the k-th digit of element num, where exp = 10^(k-1) */
int digit(int num, int exp) {
// Passing exp instead of k can avoid repeated expensive exponentiation here
return (num / exp) % 10;
}
/* Counting sort (based on nums k-th digit) */
void countingSortDigit(int[] nums, int exp) {
// Decimal digit range is 0~9, therefore need a bucket array of length 10
int[] counter = new int[10];
int n = nums.length;
// Count the occurrence of digits 0~9
for (int i = 0; i < n; i++) {
int d = digit(nums[i], exp); // Get the k-th digit of nums[i], noted as d
counter[d]++; // Count the occurrence of digit d
}
// Calculate prefix sum, converting "occurrence count" into "array index"
for (int i = 1; i < 10; i++) {
counter[i] += counter[i - 1];
}
// Traverse in reverse, based on bucket statistics, place each element into res
int[] res = new int[n];
for (int i = n - 1; i >= 0; i--) {
int d = digit(nums[i], exp);
int j = counter[d] - 1; // Get the index j for d in the array
res[j] = nums[i]; // Place the current element at index j
counter[d]--; // Decrease the count of d by 1
}
// Use result to overwrite the original array nums
for (int i = 0; i < n; i++)
nums[i] = res[i];
}
/* Radix sort */
void radixSort(int[] nums) {
// Get the maximum element of the array, used to determine the maximum number of digits
int m = Integer.MIN_VALUE;
for (int num : nums)
if (num > m)
m = num;
// Traverse from the lowest to the highest digit
for (int exp = 1; exp <= m; exp *= 10) {
// Perform counting sort on the k-th digit of array elements
// k = 1 -> exp = 1
// k = 2 -> exp = 10
// i.e., exp = 10^(k-1)
countingSortDigit(nums, exp);
}
}
radix_sort.cs
/* Get the k-th digit of element num, where exp = 10^(k-1) */
int Digit(int num, int exp) {
// Passing exp instead of k can avoid repeated expensive exponentiation here
return (num / exp) % 10;
}
/* Counting sort (based on nums k-th digit) */
void CountingSortDigit(int[] nums, int exp) {
// Decimal digit range is 0~9, therefore need a bucket array of length 10
int[] counter = new int[10];
int n = nums.Length;
// Count the occurrence of digits 0~9
for (int i = 0; i < n; i++) {
int d = Digit(nums[i], exp); // Get the k-th digit of nums[i], noted as d
counter[d]++; // Count the occurrence of digit d
}
// Calculate prefix sum, converting "occurrence count" into "array index"
for (int i = 1; i < 10; i++) {
counter[i] += counter[i - 1];
}
// Traverse in reverse, based on bucket statistics, place each element into res
int[] res = new int[n];
for (int i = n - 1; i >= 0; i--) {
int d = Digit(nums[i], exp);
int j = counter[d] - 1; // Get the index j for d in the array
res[j] = nums[i]; // Place the current element at index j
counter[d]--; // Decrease the count of d by 1
}
// Use result to overwrite the original array nums
for (int i = 0; i < n; i++) {
nums[i] = res[i];
}
}
/* Radix sort */
void RadixSort(int[] nums) {
// Get the maximum element of the array, used to determine the maximum number of digits
int m = int.MinValue;
foreach (int num in nums) {
if (num > m) m = num;
}
// Traverse from the lowest to the highest digit
for (int exp = 1; exp <= m; exp *= 10) {
// Perform counting sort on the k-th digit of array elements
// k = 1 -> exp = 1
// k = 2 -> exp = 10
// i.e., exp = 10^(k-1)
CountingSortDigit(nums, exp);
}
}
radix_sort.go
/* Get the k-th digit of element num, where exp = 10^(k-1) */
func digit(num, exp int) int {
// Passing exp instead of k can avoid repeated expensive exponentiation here
return (num / exp) % 10
}
/* Counting sort (based on nums k-th digit) */
func countingSortDigit(nums []int, exp int) {
// Decimal digit range is 0~9, therefore need a bucket array of length 10
counter := make([]int, 10)
n := len(nums)
// Count the occurrence of digits 0~9
for i := 0; i < n; i++ {
d := digit(nums[i], exp) // Get the k-th digit of nums[i], noted as d
counter[d]++ // Count the occurrence of digit d
}
// Calculate prefix sum, converting "occurrence count" into "array index"
for i := 1; i < 10; i++ {
counter[i] += counter[i-1]
}
// Traverse in reverse, based on bucket statistics, place each element into res
res := make([]int, n)
for i := n - 1; i >= 0; i-- {
d := digit(nums[i], exp)
j := counter[d] - 1 // Get the index j for d in the array
res[j] = nums[i] // Place the current element at index j
counter[d]-- // Decrease the count of d by 1
}
// Use result to overwrite the original array nums
for i := 0; i < n; i++ {
nums[i] = res[i]
}
}
/* Radix sort */
func radixSort(nums []int) {
// Get the maximum element of the array, used to determine the maximum number of digits
max := math.MinInt
for _, num := range nums {
if num > max {
max = num
}
}
// Traverse from the lowest to the highest digit
for exp := 1; max >= exp; exp *= 10 {
// Perform counting sort on the k-th digit of array elements
// k = 1 -> exp = 1
// k = 2 -> exp = 10
// i.e., exp = 10^(k-1)
countingSortDigit(nums, exp)
}
}
radix_sort.swift
/* Get the k-th digit of element num, where exp = 10^(k-1) */
func digit(num: Int, exp: Int) -> Int {
// Passing exp instead of k can avoid repeated expensive exponentiation here
(num / exp) % 10
}
/* Counting sort (based on nums k-th digit) */
func countingSortDigit(nums: inout [Int], exp: Int) {
// Decimal digit range is 0~9, therefore need a bucket array of length 10
var counter = Array(repeating: 0, count: 10)
// Count the occurrence of digits 0~9
for i in nums.indices {
let d = digit(num: nums[i], exp: exp) // Get the k-th digit of nums[i], noted as d
counter[d] += 1 // Count the occurrence of digit d
}
// Calculate prefix sum, converting "occurrence count" into "array index"
for i in 1 ..< 10 {
counter[i] += counter[i - 1]
}
// Traverse in reverse, based on bucket statistics, place each element into res
var res = Array(repeating: 0, count: nums.count)
for i in nums.indices.reversed() {
let d = digit(num: nums[i], exp: exp)
let j = counter[d] - 1 // Get the index j for d in the array
res[j] = nums[i] // Place the current element at index j
counter[d] -= 1 // Decrease the count of d by 1
}
// Use result to overwrite the original array nums
for i in nums.indices {
nums[i] = res[i]
}
}
/* Radix sort */
func radixSort(nums: inout [Int]) {
// Get the maximum element of the array, used to determine the maximum number of digits
var m = Int.min
for num in nums {
if num > m {
m = num
}
}
// Traverse from the lowest to the highest digit
for exp in sequence(first: 1, next: { m >= ($0 * 10) ? $0 * 10 : nil }) {
// Perform counting sort on the k-th digit of array elements
// k = 1 -> exp = 1
// k = 2 -> exp = 10
// i.e., exp = 10^(k-1)
countingSortDigit(nums: &nums, exp: exp)
}
}
radix_sort.js
/* Get the k-th digit of element num, where exp = 10^(k-1) */
function digit(num, exp) {
// Passing exp instead of k can avoid repeated expensive exponentiation here
return Math.floor(num / exp) % 10;
}
/* Counting sort (based on nums k-th digit) */
function countingSortDigit(nums, exp) {
// Decimal digit range is 0~9, therefore need a bucket array of length 10
const counter = new Array(10).fill(0);
const n = nums.length;
// Count the occurrence of digits 0~9
for (let i = 0; i < n; i++) {
const d = digit(nums[i], exp); // Get the k-th digit of nums[i], noted as d
counter[d]++; // Count the occurrence of digit d
}
// Calculate prefix sum, converting "occurrence count" into "array index"
for (let i = 1; i < 10; i++) {
counter[i] += counter[i - 1];
}
// Traverse in reverse, based on bucket statistics, place each element into res
const res = new Array(n).fill(0);
for (let i = n - 1; i >= 0; i--) {
const d = digit(nums[i], exp);
const j = counter[d] - 1; // Get the index j for d in the array
res[j] = nums[i]; // Place the current element at index j
counter[d]--; // Decrease the count of d by 1
}
// Use result to overwrite the original array nums
for (let i = 0; i < n; i++) {
nums[i] = res[i];
}
}
/* Radix sort */
function radixSort(nums) {
// Get the maximum element of the array, used to determine the maximum number of digits
let m = Math.max(... nums);
// Traverse from the lowest to the highest digit
for (let exp = 1; exp <= m; exp *= 10) {
// Perform counting sort on the k-th digit of array elements
// k = 1 -> exp = 1
// k = 2 -> exp = 10
// i.e., exp = 10^(k-1)
countingSortDigit(nums, exp);
}
}
radix_sort.ts
/* Get the k-th digit of element num, where exp = 10^(k-1) */
function digit(num: number, exp: number): number {
// Passing exp instead of k can avoid repeated expensive exponentiation here
return Math.floor(num / exp) % 10;
}
/* Counting sort (based on nums k-th digit) */
function countingSortDigit(nums: number[], exp: number): void {
// Decimal digit range is 0~9, therefore need a bucket array of length 10
const counter = new Array(10).fill(0);
const n = nums.length;
// Count the occurrence of digits 0~9
for (let i = 0; i < n; i++) {
const d = digit(nums[i], exp); // Get the k-th digit of nums[i], noted as d
counter[d]++; // Count the occurrence of digit d
}
// Calculate prefix sum, converting "occurrence count" into "array index"
for (let i = 1; i < 10; i++) {
counter[i] += counter[i - 1];
}
// Traverse in reverse, based on bucket statistics, place each element into res
const res = new Array(n).fill(0);
for (let i = n - 1; i >= 0; i--) {
const d = digit(nums[i], exp);
const j = counter[d] - 1; // Get the index j for d in the array
res[j] = nums[i]; // Place the current element at index j
counter[d]--; // Decrease the count of d by 1
}
// Use result to overwrite the original array nums
for (let i = 0; i < n; i++) {
nums[i] = res[i];
}
}
/* Radix sort */
function radixSort(nums: number[]): void {
// Get the maximum element of the array, used to determine the maximum number of digits
let m: number = Math.max(... nums);
// Traverse from the lowest to the highest digit
for (let exp = 1; exp <= m; exp *= 10) {
// Perform counting sort on the k-th digit of array elements
// k = 1 -> exp = 1
// k = 2 -> exp = 10
// i.e., exp = 10^(k-1)
countingSortDigit(nums, exp);
}
}
radix_sort.dart
/* Get k-th digit of element _num, where exp = 10^(k-1) */
int digit(int _num, int exp) {
// Passing exp instead of k can avoid repeated expensive exponentiation here
return (_num ~/ exp) % 10;
}
/* Counting sort (based on nums k-th digit) */
void countingSortDigit(List<int> nums, int exp) {
// Decimal digit range is 0~9, therefore need a bucket array of length 10
List<int> counter = List<int>.filled(10, 0);
int n = nums.length;
// Count the occurrence of digits 0~9
for (int i = 0; i < n; i++) {
int d = digit(nums[i], exp); // Get the k-th digit of nums[i], noted as d
counter[d]++; // Count the occurrence of digit d
}
// Calculate prefix sum, converting "occurrence count" into "array index"
for (int i = 1; i < 10; i++) {
counter[i] += counter[i - 1];
}
// Traverse in reverse, based on bucket statistics, place each element into res
List<int> res = List<int>.filled(n, 0);
for (int i = n - 1; i >= 0; i--) {
int d = digit(nums[i], exp);
int j = counter[d] - 1; // Get the index j for d in the array
res[j] = nums[i]; // Place the current element at index j
counter[d]--; // Decrease the count of d by 1
}
// Use result to overwrite the original array nums
for (int i = 0; i < n; i++) nums[i] = res[i];
}
/* Radix sort */
void radixSort(List<int> nums) {
// Get the maximum element of the array, used to determine the maximum number of digits
// In Dart, int length is 64 bits
int m = -1 << 63;
for (int _num in nums) if (_num > m) m = _num;
// Traverse from the lowest to the highest digit
for (int exp = 1; exp <= m; exp *= 10)
// Perform counting sort on the k-th digit of array elements
// k = 1 -> exp = 1
// k = 2 -> exp = 10
// i.e., exp = 10^(k-1)
countingSortDigit(nums, exp);
}
radix_sort.rs
/* Get the k-th digit of element num, where exp = 10^(k-1) */
fn digit(num: i32, exp: i32) -> usize {
// Passing exp instead of k can avoid repeated expensive exponentiation here
return ((num / exp) % 10) as usize;
}
/* Counting sort (based on nums k-th digit) */
fn counting_sort_digit(nums: &mut [i32], exp: i32) {
// Decimal digit range is 0~9, therefore need a bucket array of length 10
let mut counter = [0; 10];
let n = nums.len();
// Count the occurrence of digits 0~9
for i in 0..n {
let d = digit(nums[i], exp); // Get the k-th digit of nums[i], noted as d
counter[d] += 1; // Count the occurrence of digit d
}
// Calculate prefix sum, converting "occurrence count" into "array index"
for i in 1..10 {
counter[i] += counter[i - 1];
}
// Traverse in reverse, based on bucket statistics, place each element into res
let mut res = vec![0; n];
for i in (0..n).rev() {
let d = digit(nums[i], exp);
let j = counter[d] - 1; // Get the index j for d in the array
res[j] = nums[i]; // Place the current element at index j
counter[d] -= 1; // Decrease the count of d by 1
}
// Use result to overwrite the original array nums
nums.copy_from_slice(&res);
}
/* Radix sort */
fn radix_sort(nums: &mut [i32]) {
// Get the maximum element of the array, used to determine the maximum number of digits
let m = *nums.into_iter().max().unwrap();
// Traverse from the lowest to the highest digit
let mut exp = 1;
while exp <= m {
counting_sort_digit(nums, exp);
exp *= 10;
}
}
radix_sort.c
/* Get the k-th digit of element num, where exp = 10^(k-1) */
int digit(int num, int exp) {
// Passing exp instead of k can avoid repeated expensive exponentiation here
return (num / exp) % 10;
}
/* Counting sort (based on nums k-th digit) */
void countingSortDigit(int nums[], int size, int exp) {
// Decimal digit range is 0~9, therefore need a bucket array of length 10
int *counter = (int *)malloc((sizeof(int) * 10));
memset(counter, 0, sizeof(int) * 10); // Initialize to 0 to support subsequent memory release
// Count the occurrence of digits 0~9
for (int i = 0; i < size; i++) {
// Get the k-th digit of nums[i], noted as d
int d = digit(nums[i], exp);
// Count the occurrence of digit d
counter[d]++;
}
// Calculate prefix sum, converting "occurrence count" into "array index"
for (int i = 1; i < 10; i++) {
counter[i] += counter[i - 1];
}
// Traverse in reverse, based on bucket statistics, place each element into res
int *res = (int *)malloc(sizeof(int) * size);
for (int i = size - 1; i >= 0; i--) {
int d = digit(nums[i], exp);
int j = counter[d] - 1; // Get the index j for d in the array
res[j] = nums[i]; // Place the current element at index j
counter[d]--; // Decrease the count of d by 1
}
// Use result to overwrite the original array nums
for (int i = 0; i < size; i++) {
nums[i] = res[i];
}
// Free memory
free(res);
free(counter);
}
/* Radix sort */
void radixSort(int nums[], int size) {
// Get the maximum element of the array, used to determine the maximum number of digits
int max = INT32_MIN;
for (int i = 0; i < size; i++) {
if (nums[i] > max) {
max = nums[i];
}
}
// Traverse from the lowest to the highest digit
for (int exp = 1; max >= exp; exp *= 10)
// Perform counting sort on the k-th digit of array elements
// k = 1 -> exp = 1
// k = 2 -> exp = 10
// i.e., exp = 10^(k-1)
countingSortDigit(nums, size, exp);
}
radix_sort.kt
/* Get the k-th digit of element num, where exp = 10^(k-1) */
fun digit(num: Int, exp: Int): Int {
// Passing exp instead of k can avoid repeated expensive exponentiation here
return (num / exp) % 10
}
/* Counting sort (based on nums k-th digit) */
fun countingSortDigit(nums: IntArray, exp: Int) {
// Decimal digit range is 0~9, therefore need a bucket array of length 10
val counter = IntArray(10)
val n = nums.size
// Count the occurrence of digits 0~9
for (i in 0..<n) {
val d = digit(nums[i], exp) // Get the k-th digit of nums[i], noted as d
counter[d]++ // Count the occurrence of digit d
}
// Calculate prefix sum, converting "occurrence count" into "array index"
for (i in 1..9) {
counter[i] += counter[i - 1]
}
// Traverse in reverse, based on bucket statistics, place each element into res
val res = IntArray(n)
for (i in n - 1 downTo 0) {
val d = digit(nums[i], exp)
val j = counter[d] - 1 // Get the index j for d in the array
res[j] = nums[i] // Place the current element at index j
counter[d]-- // Decrease the count of d by 1
}
// Use result to overwrite the original array nums
for (i in 0..<n)
nums[i] = res[i]
}
/* Radix sort */
fun radixSort(nums: IntArray) {
// Get the maximum element of the array, used to determine the maximum number of digits
var m = Int.MIN_VALUE
for (num in nums) if (num > m) m = num
var exp = 1
// Traverse from the lowest to the highest digit
while (exp <= m) {
// Perform counting sort on the k-th digit of array elements
// k = 1 -> exp = 1
// k = 2 -> exp = 10
// i.e., exp = 10^(k-1)
countingSortDigit(nums, exp)
exp *= 10
}
}
radix_sort.rb
### Get k-th digit of element num, where exp = 10^(k-1) ###
def digit(num, exp)
# Passing exp instead of k avoids expensive exponentiation calculations
(num / exp) % 10
end
### Counting sort (sort by k-th digit of nums) ###
def counting_sort_digit(nums, exp)
# Decimal digit range is 0~9, therefore need a bucket array of length 10
counter = Array.new(10, 0)
n = nums.length
# Count the occurrence of digits 0~9
for i in 0...n
d = digit(nums[i], exp) # Get the k-th digit of nums[i], noted as d
counter[d] += 1 # Count the occurrence of digit d
end
# Calculate prefix sum, converting "occurrence count" into "array index"
(1...10).each { |i| counter[i] += counter[i - 1] }
# Traverse in reverse, based on bucket statistics, place each element into res
res = Array.new(n, 0)
for i in (n - 1).downto(0)
d = digit(nums[i], exp)
j = counter[d] - 1 # Get the index j for d in the array
res[j] = nums[i] # Place the current element at index j
counter[d] -= 1 # Decrease the count of d by 1
end
# Use result to overwrite the original array nums
(0...n).each { |i| nums[i] = res[i] }
end
### Radix sort ###
def radix_sort(nums)
# Get the maximum element of the array, used to determine the maximum number of digits
m = nums.max
# Traverse from the lowest to the highest digit
exp = 1
while exp <= m
# Perform counting sort on the k-th digit of array elements
# k = 1 -> exp = 1
# k = 2 -> exp = 10
# i.e., exp = 10^(k-1)
counting_sort_digit(nums, exp)
exp *= 10
end
end
Why start sorting from the lowest digit?
In successive sorting passes, a later pass overrides the result of an earlier one. For example, if the first pass yields \(a < b\) but the second yields \(a > b\), then the result of the second pass prevails. Because higher-order digits have higher priority than lower-order digits, we should sort the lower digits first and then the higher digits.
11.10.2 Algorithm Characteristics¶
Compared with counting sort, radix sort is suitable for larger value ranges, but only when the data can be represented with a fixed number of digits and that digit count is not too large. For example, floating-point numbers are not well suited to radix sort because the digit count \(k\) can be too large, potentially leading to time complexity \(O(nk) \gg O(n^2)\).
- Time complexity of \(O(nk)\), non-adaptive sorting: Let the number of items be \(n\), let the values be represented in base \(d\), and let the maximum number of digits be \(k\). Counting sort on one digit takes \(O(n + d)\) time, so sorting all \(k\) digits takes \(O((n + d)k)\) time. In practice, \(d\) and \(k\) are usually relatively small, so the overall time complexity approaches \(O(n)\).
- Space complexity of \(O(n + d)\), non-in-place sorting: Same as counting sort, radix sort requires auxiliary arrays
resandcounterof lengths \(n\) and \(d\). - Stable sort: When counting sort is stable, radix sort is also stable; when counting sort is unstable, radix sort cannot guarantee correct sorting results.