Radix Sort
Last updated
Radix sort is a non-comparison sort for integers. Instead of comparing values, it sorts numbers digit by digit. The least-significant-digit (LSD) version processes the ones digit first, then the tens, then the hundreds, using a stable counting sort at each digit. Because each pass is stable, once the most significant digit is processed the whole array is sorted. Press play above to watch each digit pass reorder the bars.
Radix sort runs in O(d·(n + k)) time, where d is the number of digits and k is the base (10 here). For fixed-width integers this is effectively linear - it can beat O(n log n) comparison sorts - but it only works on data that can be broken into digits or keys.
Time & space complexity
| Case | Complexity | Notes |
|---|---|---|
| Time | O(d·(n + k)) | d digits, base k (linear for fixed d) |
| Space | O(n + k) | Output array + digit counts |
| Stable | Yes | Each digit pass is a stable counting sort |
| Comparison? | No | Sorts by digit, not by comparing values |
| Works on | Integers/keys | Not general comparable objects |
Step by step
| Step | What happens |
|---|---|
| 1 | Find the maximum value to know how many digits to process. |
| 2 | Start with the least-significant digit (the ones place). |
| 3 | Stably sort the array by that digit using counting sort. |
| 4 | Move to the next more-significant digit. |
| 5 | Repeat until all digit positions are processed. |
Worked example
Sorting [170, 45, 75, 90, 2, 24, 66]:
| Pass | Array | Action |
|---|---|---|
| Start | [170, 45, 75, 90, 2, 24, 66] | Max is 170, so three digit passes are needed. |
| Ones | [170, 90, 2, 24, 45, 75, 66] | Stable sort by the ones digit: 0, 0, 2, 4, 5, 5, 6. |
| Tens | [2, 24, 45, 66, 170, 75, 90] | Stable sort by the tens digit: 0, 2, 4, 6, 7, 7, 9 (170 keeps its lead over 75). |
| Hundreds | [2, 24, 45, 66, 75, 90, 170] | Stable sort by the hundreds digit; only 170 has a 1, so it moves last. Sorted. |
When to use radix sort
| Use it when | Avoid it when |
|---|---|
| Keys are integers or fixed-length strings you can split into digits. | You must sort arbitrary objects by a custom comparator. |
Keys have a small, bounded number of digits d, so O(d·(n + k)) beats O(n log n). | Keys are very long or unbounded, making d large and the passes expensive. |
You need a stable sort and can afford O(n + k) extra space. | Memory is tight and the O(n + k) buffers are unacceptable. |
The value range or base k is modest relative to n. | k is huge, so each counting-sort pass dominates the running time. |
Radix Sort code
A clean, runnable Radix Sort implementation in Python, JavaScript, Java, C++, C. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.
Radix Sort code in Python
Python
1def radix_sort(a):2 # Sort by each decimal digit, least significant first3 max_value = max(a)4 exp = 15 while max_value // exp > 0:6 a = sort_by_digit(a, exp)7 exp *= 108 return a9
10
11def sort_by_digit(a, exp):12 buckets = [[] for _ in range(10)]13 for value in a:14 digit = (value // exp) % 1015 buckets[digit].append(value)16 # Concatenating buckets 0..9 keeps the sort stable17 return [value for bucket in buckets for value in bucket]18
19
20nums = [170, 45, 75, 90, 802, 24, 2, 66]21print("Before:", nums)22print("After: ", radix_sort(nums))Radix Sort code in JavaScript
JavaScript
1function radixSort(arr) {2 let a = [...arr];3 const max = Math.max(...a);4 // One counting pass per digit, least significant first5 for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {6 const buckets = Array.from({ length: 10 }, () => []);7 for (const x of a) {8 buckets[Math.floor(x / exp) % 10].push(x);9 }10 a = buckets.flat();11 }12 return a;13}14
15const data = [170, 45, 75, 90, 802, 24, 2, 66];16console.log("Before:", data);17console.log("Sorted:", radixSort(data));Radix Sort code in Java
Java
1import java.util.Arrays;2
3public class Main {4 static void radixSort(int[] arr) {5 int max = 0;6 for (int v : arr) max = Math.max(max, v);7 // One stable counting pass per decimal digit8 for (int exp = 1; max / exp > 0; exp *= 10) countingPass(arr, exp);9 }10
11 static void countingPass(int[] arr, int exp) {12 int n = arr.length;13 int[] out = new int[n];14 int[] count = new int[10];15 for (int v : arr) count[(v / exp) % 10]++;16 for (int i = 1; i < 10; i++) count[i] += count[i - 1];17 // Walk backwards to keep the pass stable18 for (int i = n - 1; i >= 0; i--) {19 int digit = (arr[i] / exp) % 10;20 out[--count[digit]] = arr[i];21 }22 System.arraycopy(out, 0, arr, 0, n);23 }24
25 public static void main(String[] args) {26 int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};27 System.out.println("Before: " + Arrays.toString(arr));28 radixSort(arr);29 System.out.println("After: " + Arrays.toString(arr));30 }31}Radix Sort code in C++
C++
1#include <algorithm>2#include <iostream>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10// Stable counting sort on one decimal digit (exp = 1, 10, 100, ...)11void countingPass(std::vector<int>& a, int exp) {12 std::vector<int> output(a.size());13 std::vector<int> count(10, 0);14 for (int x : a) ++count[(x / exp) % 10];15 for (int d = 1; d < 10; ++d) count[d] += count[d - 1];16 for (int i = static_cast<int>(a.size()) - 1; i >= 0; --i) {17 int digit = (a[i] / exp) % 10;18 output[--count[digit]] = a[i];19 }20 a = output;21}22
23void radixSort(std::vector<int>& a) {24 int maxVal = *std::max_element(a.begin(), a.end());25 for (int exp = 1; maxVal / exp > 0; exp *= 10) {26 countingPass(a, exp);27 }28}29
30int main() {31 std::vector<int> data = {170, 45, 75, 90, 802, 24, 2, 66};32 std::cout << "Before: ";33 printVec(data);34 radixSort(data);35 std::cout << "After: ";36 printVec(data);37 return 0;38}Radix Sort code in C
C
1#include <stdio.h>2#include <stdlib.h>3
4void printArr(const int a[], int n) {5 for (int i = 0; i < n; i++) printf("%d ", a[i]);6 printf("\n");7}8
9// Stable counting sort on one decimal digit (exp = 1, 10, 100, ...)10void countingPass(int a[], int n, int exp) {11 int* output = malloc(n * sizeof(int));12 int count[10] = {0};13 for (int i = 0; i < n; i++) count[(a[i] / exp) % 10]++;14 for (int d = 1; d < 10; d++) count[d] += count[d - 1];15 for (int i = n - 1; i >= 0; i--) {16 int digit = (a[i] / exp) % 10;17 output[--count[digit]] = a[i];18 }19 for (int i = 0; i < n; i++) a[i] = output[i];20 free(output);21}22
23void radixSort(int a[], int n) {24 int maxVal = a[0];25 for (int i = 1; i < n; i++) {26 if (a[i] > maxVal) maxVal = a[i];27 }28 for (int exp = 1; maxVal / exp > 0; exp *= 10) {29 countingPass(a, n, exp);30 }31}32
33int main(void) {34 int data[] = {170, 45, 75, 90, 802, 24, 2, 66};35 int n = sizeof(data) / sizeof(data[0]);36 printf("Before: ");37 printArr(data, n);38 radixSort(data, n);39 printf("After: ");40 printArr(data, n);41 return 0;42}Radix Sort FAQ
What is the time complexity of radix sort?
Radix sort is
O(d·(n + k)), where d is the number of digits and k is the base. For integers of fixed width this is effectively O(n), which can be faster than comparison sorts. It uses O(n + k) extra space.Is radix sort stable?
Yes. LSD radix sort relies on a stable counting sort at each digit; stability is what makes the digit-by-digit approach produce a correctly sorted result.
When can I use radix sort?
Radix sort works on data that can be decomposed into digits or fixed-size keys, such as integers or fixed-length strings. It is not a general-purpose comparison sort, so it cannot sort arbitrary objects by a custom comparator.
How is radix sort different from counting sort?
Counting sort sorts by a single key in one pass and needs a count array as large as the value range, so it degrades when values are spread out. Radix sort applies counting sort digit by digit, keeping each pass's count array small (base
k), which lets it handle large value ranges that plain counting sort could not.Why does LSD radix sort start with the least-significant digit?
Starting from the least-significant digit lets each stable pass preserve the ordering established by all earlier, less-significant digits. By the time the most-significant digit is processed, ties on that digit are already correctly ordered by the lower digits, so the array ends up fully sorted. Sorting from the most-significant digit first would break this and require a different, recursive approach (MSD radix sort).
Can radix sort handle negative numbers?
Not directly - the basic digit extraction assumes non-negative integers. Common fixes are to offset all values by adding the minimum so everything is non-negative, or to sort the negatives and non-negatives separately and then concatenate. Ignoring this is a frequent bug when applying radix sort to real data.
Related resources
More visualizations
