Radix Sort
In this page:
Basic Idea
Radix sort sorts numbers digit by digit, from the least significant digit to the most significant, using a stable sort like counting sort as a subroutine at each digit position — it sidesteps comparing whole numbers directly.
Example: Basic Idea
#include <iostream>
using namespace std;
int main() {
int arr[] = {170, 45, 75, 90, 802, 24};
int n = 6;
for (int exp = 1; 802 / exp > 0; exp *= 10) {
int output[6], count[10] = {0};
for (int i = 0; i < n; i++) count[(arr[i] / exp) % 10]++;
for (int i = 1; i < 10; i++) count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) { int d = (arr[i] / exp) % 10; output[--count[d]] = arr[i]; }
for (int i = 0; i < n; i++) arr[i] = output[i];
}
for (int x : arr) cout << x << " ";
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {170, 45, 75, 90, 802, 24};
int n = arr.length;
for (int exp = 1; 802 / exp > 0; exp *= 10) {
int[] output = new int[n], count = new int[10];
for (int x : arr) count[(x / exp) % 10]++;
for (int i = 1; i < 10; i++) count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) { int d = (arr[i] / exp) % 10; output[--count[d]] = arr[i]; }
arr = output;
}
System.out.println(java.util.Arrays.toString(arr));
}
}arr = [170, 45, 75, 90, 802, 24]
exp = 1
while 802 // exp > 0:
n = len(arr)
output = [0] * n
count = [0] * 10
for x in arr:
count[(x // exp) % 10] += 1
for i in range(1, 10):
count[i] += count[i - 1]
for i in range(n - 1, -1, -1):
d = (arr[i] // exp) % 10
count[d] -= 1
output[count[d]] = arr[i]
arr = output
exp *= 10
print(arr)#include <stdio.h>
int main() {
int arr[] = {170, 45, 75, 90, 802, 24};
int n = 6;
for (int exp = 1; 802 / exp > 0; exp *= 10) {
int output[6], count[10] = {0};
for (int i = 0; i < n; i++) count[(arr[i] / exp) % 10]++;
for (int i = 1; i < 10; i++) count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) { int d = (arr[i] / exp) % 10; output[--count[d]] = arr[i]; }
for (int i = 0; i < n; i++) arr[i] = output[i];
}
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
return 0;
}Login to try C/C++/Java code in the editor
Step by Step
Each pass sorts the entire array by just one digit position while preserving the relative order of equal digits from the previous pass (which is why the subroutine must be stable) — after processing every digit position, the array ends up fully sorted.
Example: Step by Step
#include <iostream>
using namespace std;
int main() {
cout << "Sort by ones digit first using counting sort, then tens digit, then hundreds, preserving prior order";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Sort by ones digit first using counting sort, then tens digit, then hundreds, preserving prior order");
}
}print("Sort by ones digit first using counting sort, then tens digit, then hundreds, preserving prior order")#include <stdio.h>
int main() {
printf("Sort by ones digit first using counting sort, then tens digit, then hundreds, preserving prior order");
return 0;
}Login to try C/C++/Java code in the editor
Small Array
Tracing radix sort on small numbers like [170, 45, 75, 90, 802, 24] shows how sorting by the ones digit first, then the tens digit, then the hundreds digit, progressively refines the order until the final pass leaves the array fully sorted.
Example: Small Array
#include <iostream>
using namespace std;
int main() {
int arr[] = {170, 45, 75, 90, 802, 24};
for (int x : arr) cout << "ones digit of " << x << " is " << x % 10 << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {170, 45, 75, 90, 802, 24};
for (int x : arr) System.out.println("ones digit of " + x + " is " + x % 10);
}
}arr = [170, 45, 75, 90, 802, 24]
for x in arr:
print("ones digit of", x, "is", x % 10)#include <stdio.h>
int main() {
int arr[] = {170, 45, 75, 90, 802, 24};
for (int i = 0; i < 6; i++) printf("ones digit of %d is %d\n", arr[i], arr[i] % 10);
return 0;
}Login to try C/C++/Java code in the editor
Practice
Radix sort is worth comparing against counting sort on the same data: counting sort needs a count array sized to the largest value directly, while radix sort processes that same value digit by digit, trading a huge range for a bounded number of passes.
Example: Practice
#include <iostream>
using namespace std;
int main() {
cout << "Counting sort needs a count array sized to the largest value; radix sort avoids that by sorting per digit";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Counting sort needs a count array sized to the largest value; radix sort avoids that by sorting per digit");
}
}print("Counting sort needs a count array sized to the largest value; radix sort avoids that by sorting per digit")#include <stdio.h>
int main() {
printf("Counting sort needs a count array sized to the largest value; radix sort avoids that by sorting per digit");
return 0;
}Login to try C/C++/Java code in the editor
Summary
Radix sort runs in O(d * (n + k)) time, where d is the number of digits and k is the base used per digit (usually 10) — for fixed-width numbers this is effectively linear, making it faster than comparison sorts on the right kind of data.
Example: Summary
#include <iostream>
using namespace std;
int main() {
cout << "Radix sort: O(d * (n + k)) time, where d is the number of digits and k is the base (usually 10)";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Radix sort: O(d * (n + k)) time, where d is the number of digits and k is the base (usually 10)");
}
}print("Radix sort: O(d * (n + k)) time, where d is the number of digits and k is the base (usually 10)")#include <stdio.h>
int main() {
printf("Radix sort: O(d * (n + k)) time, where d is the number of digits and k is the base (usually 10)");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 9 topics to unlock
0/9 topics done
Complete these topics first: