← Back to DSA Course | Chapter 9: Sorting Algorithms | Lesson 8 of 9

Radix Sort

Radix sort is like sorting mail by the last digit first, then the next digit, and so on until the whole pile is sorted.

In this page:

  1. Basic Idea
  2. Step by Step
  3. Small Array
  4. Practice
  5. Summary
Syntax
markup 
exp = 1
while max_value // exp > 0:
    counting_sort_by_digit(arr, exp)
    exp *= 10

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;
}

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;
}

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;
}

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;
}

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;
}
Related Topics

Counting Sort · Heap Sort · Quick Sort · Merge Sort

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
Common Mistakes
  1. Using an unstable sort for each digit pass, which breaks the ordering from earlier passes.
  2. Starting from the most significant digit with the least significant digit's method.
  3. Stopping the exp loop too early, so numbers with more digits than maxVal are not fully sorted.
🔒

Chapter Quiz — Complete all 9 topics to unlock

0/9 topics done

Complete these topics first:

← Previous Lesson Counting Sort Next Lesson → Sorting Comparison

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.