When you first learn about sorting, you probably start with algorithms that compare numbers, such as “Is 5 greater than 3?” While intuitive, these comparison-based methods have a mathematical speed limit. If you are dealing with massive datasets of integers or strings, you need a different strategy. This is where DSA radix sort comes into play. Instead of comparing the whole value of two numbers, it looks at the individual digits that make them up.
What is Radix Sort?
To answer the question, “What is radix sort?”, we have to look at the word “radix”. In mathematics, the radix (or base) is the number of unique digits used to represent numbers. For our standard decimal system, the radix is 10.
DSA radix sort is a linear sorting algorithm that avoids comparisons. It works by grouping numbers based on their individual digits. To keep the sort accurate, it processes these digits in a specific order: usually from the Least Significant Digit (LSD) on the right to the Most Significant Digit (MSD) on the left.
For it to work, it requires a “stable” secondary sorting algorithm to handle the individual digits. A sort is stable if it keeps the relative order of items with the same value. Most implementations use Counting Sort as this helper because it is fast and handles small ranges of numbers (0-9) perfectly.
How the DSA Radix Sort Algorithm Works?
The logic behind this method is quite elegant. Imagine you have a pile of three-digit numbers. Here is the step-by-step breakdown of the process:
- Find the Maximum: Identify the largest number in the list to determine how many digits we need to process.
- Sort by Units: Sort the entire list based on the digits in the units place (10^0).
- Sort by Tens: Sort the first pass result by the digits in the tens place (10^1).
- Sort by Hundreds: Continue this for the hundreds, thousands, and so on.
- Completion: Once you have processed the most significant digit, the entire list is sorted.
A Detailed DSA Radix Sort Example
Let’s trace a radix sort example to see the “magic” in action. Suppose we have the following array: [170, 45, 75, 90, 802, 24, 2, 66].
Pass 1: The Ones’ Place
We look at the last digit of each number: 170, 045, 075, 090, 802, 024, 002, 066.
- Sorted by ones: [170, 90, 802, 2, 24, 45, 75, 66]
Pass 2: The Tens Place
Now we look at the second digit: 170, 090, 802, 002, 024, 045, 075, 066.
- Sorted by tens: [802, 2, 24, 45, 66, 170, 75, 90]
Pass 3: The Hundreds Place
Finally, we look at the third digit: 802, 002, 024, 045, 066, 170, 075, 090.
- Sorted by hundreds: [002, 024, 045, 066, 075, 090, 170, 802]
In just three passes, the entire list is perfectly ordered. This DSA radix sort example highlights how the algorithm builds the final order layer by layer.
DSA Radix Sort in C++
If you are a developer, you will likely need to write this out. Here is a clean, efficient version of DSA radix sort in C++ using counting sort as the helper function.
#include <iostream>
#include <vector>
#include <algorithm>
// Helper to get the maximum value
int getMax(int arr[], int n) {
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx) mx = arr[i];
return mx;
}
// Stable counting sort for a specific digit (exp is 10^i)
void countSort(int arr[], int n, int exp) {
int output[n];
int i, count[10] = {0};
for (i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
for (i = 1; i < 10; i++)
count[i] += count[i – 1];
for (i = n – 1; i >= 0; i–) {
output[count[(arr[i] / exp) % 10] – 1] = arr[i];
count[(arr[i] / exp) % 10]–;
}
for (i = 0; i < n; i++)
arr[i] = output[i];
}
void radixSort(int arr[], int n) {
int m = getMax(arr, n);
// Process each digit place: 1, 10, 100…
for (int exp = 1; m / exp > 0; exp *= 10)
countSort(arr, n, exp);
}
This implementation of DSA radix sort in C++ is highly efficient for large arrays of integers.
Also Read:
- DSA Introduction
- DSA Simple Algorithm
- Advanced DSA for Students
- Advance Data Structure and Algorithms
- DSA Arrays
Complexity and Performance in DSA Radix
Is radix sort always the best choice? Not necessarily. Let’s look at the numbers.
- Time Complexity: O(d * (n + k)), where n is the number of elements, k is the range of the digits (usually 10), and d is the number of digits in the maximum number.
- Space Complexity: O(n + k), as we need extra space for the output array and the count array.
Compared to QuickSort or MergeSort (which are O(n log n)), Radix Sort can actually be faster (approaching O(n)) if the number of digits (d) is small compared to the total number of elements (n).
Radix Sort vs. Other Sorting Algorithms
| Feature | Radix Sort | Quick Sort | Counting Sort |
| Type | Non-comparative | Comparative | Non-comparative |
| Best Case | O(d * (n + k)) | O(n log n) | O(n + k) |
| Stability | Yes | No | Yes |
| Data Type | Integers/Strings | Any | Integers (small range) |
Why Should You Use Radix Sort?
While comparison sorts are excellent for general purposes,It shines in specific scenarios:
- Fixed-Length Keys: When you are sorting things like zip codes, phone numbers, or dates.
- Large N, Small D: When you have millions of records but each record has a relatively small number of digits.
Stability Requirements: When you need to maintain the original order of equal elements.
FAQs
Q1: What is radix sort's main limitation?
The main limitation is that it is data-dependent. It works best for integers or strings with a fixed radix. It is much harder to implement for floating-point numbers or complex objects.
Q2: Is Radix Sort better than QuickSort?
In terms of theoretical time complexity, it can be. However, in practice, QuickSort often performs better due to its lower overhead and better "cache locality", unless the range of digits is very small.
Q3: Can I use radix sort for strings?
Yes! A radix sort example for strings would involve sorting by characters (A-Z) instead of digits (0-9), starting with the last letter of the word.
Q4: Why is counting sort used inside radix sort?
Counting Sort is fast and stable, making it ideal for sorting digits (0-9). This stability guarantees that the work from previous digit passes remains intact.
Q5: Is DSA-radix sort an in-place algorithm?
No. It requires an auxiliary output array to store the sorted results during each pass, meaning it uses more memory than algorithms like HeapSort or QuickSort.