Sorting plays an important role in programming and data processing. Whenever we deal with numbers or words that need to be arranged in order, sorting algorithms come into play. Among many sorting techniques, Radix Sort stands out as one of the most efficient and interesting algorithms, especially when dealing with large numbers. Unlike comparison-based sorting algorithms such as Quick Sort or Heap Sort, Radix Sort works by grouping numbers based on their digits. It doesn’t compare elements directly but sorts them digit by digit — starting from the least significant digit (rightmost) to the most significant (leftmost).
with hands-on learning.
get the skills and confidence to land your next move.
Radix Sort is especially useful when we need to sort large sets of integers or even strings that represent numbers. It is a non-comparison-based sorting algorithm, which means its time complexity can be better than O(n log n) for some datasets. In fact, its performance is often O(nk), where n is the number of elements and k is the number of digits in the largest number. This makes it very efficient for uniformly sized data like IDs, zip codes, or phone numbers.
In this article, we will walk through several C++ programs to implement Radix Sort in simple and different ways — from the basic iterative approach to recursive variations. Each example will use predefined data to help beginners focus on understanding the logic clearly without worrying about user input.
Program 1: Basic Radix Sort using Loops
This is the simplest version of Radix Sort in C++. It uses the standard approach where sorting happens digit by digit using Counting Sort as a helper function. The code sorts numbers in ascending order.
#include <iostream>
using namespace std;
// Function to get the maximum value in the array
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;
}
// Counting Sort used by Radix Sort
void countSort(int arr[], int n, int exp) {
int output[n];
int 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--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
// Main Radix Sort Function
void radixSort(int arr[], int n) {
int m = getMax(arr, n);
for (int exp = 1; m / exp > 0; exp *= 10)
countSort(arr, n, exp);
}
int main() {
int arr[] {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr) / sizeof(arr[0]);
radixSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}In this version, the algorithm first finds the largest number in the array to know how many digits it needs to sort. Then it repeatedly applies counting sort on each digit. The key idea is that sorting from the least significant to the most significant digit keeps the order consistent. Beginners can easily follow this logic since it uses loops and straightforward functions.
Program 2: Recursive Implementation of Radix Sort
Now let’s look at a recursive version of Radix Sort. Here, we replace loops with recursive calls to handle each digit level, which gives learners a fresh way to visualize how the sorting process moves from one digit to another.
#include <iostream>
using namespace std;
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;
}
void countSortRecursive(int arr[], int n, int exp) {
int output[n];
int 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--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
void radixSortRecursive(int arr[], int n, int exp, int maxVal) {
if (maxVal / exp == 0)
return;
countSortRecursive(arr, n, exp);
radixSortRecursive(arr, n, exp * 10, maxVal);
}
int main() {
int arr[] {12, 89, 34, 56, 78, 9, 23};
int n = sizeof(arr) / sizeof(arr[0]);
int maxVal = getMax(arr, n);
radixSortRecursive(arr, n, 1, maxVal);
cout << "Sorted array using recursion: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}This program works the same way as the first one, but instead of looping through each digit, the function calls itself recursively for the next digit position. This approach helps beginners understand how recursion simplifies iterative processes and can make algorithms easier to follow conceptually.
Program 3: Radix Sort for Descending Order
In some cases, we may need to sort numbers from largest to smallest. This version of Radix Sort modifies the counting step slightly to achieve descending order instead of ascending.
#include <iostream>
using namespace std;
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;
}
void countSortDescending(int arr[], int n, int exp) {
int output[n];
int count[10] = {0};
for (int i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
for (int i = 8; i >= 0; i--)
count[i] += count[i + 1];
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
void radixSortDescending(int arr[], int n) {
int m = getMax(arr, n);
for (int exp = 1; m / exp > 0; exp *= 10)
countSortDescending(arr, n, exp);
}
int main() {
int arr[] {91, 54, 73, 22, 31, 65, 10};
int n = sizeof(arr) / sizeof(arr[0]);
radixSortDescending(arr, n);
cout << "Sorted array in descending order: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}Here, the main difference is in the counting phase. By reversing how the count array accumulates, we effectively reverse the sorting order. This is an excellent way for beginners to see how simple changes in logic can completely alter an algorithm’s output behavior.
Program 4: Radix Sort for Strings of Digits
Radix Sort can also handle strings of digits, such as identification numbers or numeric codes. This version uses strings and sorts them lexicographically as numbers.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// Function to get the maximum length of strings
int getMaxLength(vector<string> &arr) {
int maxLen = 0;
for (string num : arr)
if (num.length() > maxLen)
maxLen = num.length();
return maxLen;
}
// Radix Sort for strings representing numbers
void radixSortStrings(vector<string> &arr) {
int maxLen = getMaxLength(arr);
// Left-pad strings with zeros to match max length
for (int i = 0; i < arr.size(); i++)
while (arr[i].length() < maxLen)
arr[i] = "0" + arr[i];
// Perform Radix Sort digit by digit (right to left)
for (int pos = maxLen - 1; pos >= 0; pos--) {
vector<vector<string>> buckets(10);
for (string num : arr) {
int index = num[pos] - '0';
buckets[index].push_back(num);
}
arr.clear();
for (int i = 0; i < 10; i++)
for (string num : buckets[i])
arr.push_back(num);
}
// Remove leading zeros
for (int i = 0; i < arr.size(); i++)
while (arr[i].length() > 1 && arr[i][0] == '0')
arr[i].erase(0, 1);
}
int main() {
vector<string> arr {"102", "45", "7", "230", "19", "88"};
radixSortStrings(arr);
cout << "Sorted string numbers: ";
for (string num : arr)
cout << num << " ";
cout << endl;
return 0;
}This program extends Radix Sort’s usefulness to string-based data. By treating each character as a digit, the algorithm can sort numerical strings with varying lengths. This is especially useful in data processing or database systems where numbers are stored as strings.
Frequently Asked Questions (FAQ)
Here are some common questions beginners ask about Radix Sort in C++.
Q1: What is Radix Sort in C++?
Radix Sort is a non-comparison sorting algorithm that sorts numbers digit by digit, starting from the least significant to the most significant digit.
Q2: Why is Radix Sort faster than other algorithms?
It doesn’t compare elements directly. Instead, it distributes elements based on their digits, which makes it run in O(nk) time for numbers with fixed digit lengths.
Q3: Can Radix Sort handle negative numbers?
Traditional Radix Sort works only with non-negative integers, but with some modifications, it can be extended to handle negatives too.
Q4: Is Radix Sort stable?
Yes, Radix Sort is stable when its internal counting sort is stable. This means that equal elements retain their original order.
Q5: Can we use Radix Sort for strings?
Yes, as shown above, it can be easily adapted to sort strings containing digits or even alphabetical characters.
Conclusion
Radix Sort is one of the most interesting sorting algorithms in computer science because it uses a unique digit-based approach rather than direct comparisons. It is fast, efficient, and particularly useful when dealing with numbers that have a similar range or length. In this article, we explored several versions of the C++ Radix Sort program, including the basic iterative version, a recursive version, descending order sorting, and even sorting string-based numbers.
By practicing these programs, beginners can gain a deeper understanding of how Radix Sort organizes data at the digit level and how it differs from traditional sorting methods. Keep experimenting with different datasets, modify the base or digit positions, and observe the results. With a little practice, you’ll master one of the most efficient sorting techniques in C++.
