Sorting is one of the most important operations in computer programming. It helps organize data so that it can be searched, analyzed, and processed efficiently. Whether you’re building a student records system, managing inventory data, or handling large lists of numbers, sorting algorithms ensure that your program runs smoothly and efficiently.
with hands-on learning.
get the skills and confidence to land your next move.
Among the many sorting algorithms available in C, Radix Sort stands out for its unique approach. Unlike comparison-based algorithms like Quick Sort or Merge Sort, Radix Sort works by sorting numbers digit by digit — starting from the least significant digit and moving toward the most significant one. It uses another algorithm, such as Counting Sort, as a subroutine to arrange the digits. This makes Radix Sort very fast for numbers with a fixed number of digits, especially when working with large datasets.
Program 1: Basic Radix Sort Using Loops
Let’s start with a simple implementation of Radix Sort using loops. This version is designed to be easy to understand for beginners learning how sorting by digits works in C.
#include <stdio.h>
int getMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max)
max = arr[i];
return max;
}
void countingSort(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 radixSort(int arr[], int n) {
int max = getMax(arr, n);
for (int exp = 1; max / exp > 0; exp *= 10)
countingSort(arr, n, exp);
}
int main() {
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
radixSort(arr, n);
printf("Sorted array:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}In this version, the program first finds the maximum number in the array to determine the number of digits it has. It then sorts the array one digit at a time using Counting Sort as a helper function. The exp variable represents the place value — first units, then tens, then hundreds, and so on. This loop continues until all digits have been processed. This program is easy to follow and helps beginners see how sorting by individual digits can lead to a completely sorted list.
Program 2: Recursive Implementation of Radix Sort
In this version, we use recursion instead of loops to make the logic more modular and elegant. Although recursion isn’t commonly used in Radix Sort, it’s a good learning exercise for beginners who want to understand how recursive calls can replace repetitive loops.
#include <stdio.h>
int getMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max)
max = arr[i];
return max;
}
void countingSortRecursive(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 max) {
if (max / exp == 0)
return;
countingSortRecursive(arr, n, exp);
radixSortRecursive(arr, n, exp * 10, max);
}
int main() {
int arr[] = {329, 457, 657, 839, 436, 720, 355};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
int max = getMax(arr, n);
radixSortRecursive(arr, n, 1, max);
printf("Sorted array:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}In this recursive version, the program replaces the loop in radixSort() with a recursive function that calls itself for each digit position. The base case stops the recursion when the maximum number’s highest digit has been processed. This approach not only works effectively but also deepens understanding of recursive logic and function calls. It’s especially useful for students who want to see how recursion can be applied to traditional iterative algorithms.
Program 3: Radix Sort with User Input
Now let’s make the program interactive. In this version, users can enter their own list of numbers, and the program will sort them using Radix Sort. This helps learners practice both sorting and user input handling in C.
#include <stdio.h>
int getMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max)
max = arr[i];
return max;
}
void countingSort(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 radixSort(int arr[], int n) {
int max = getMax(arr, n);
for (int exp = 1; max / exp > 0; exp *= 10)
countingSort(arr, n, exp);
}
int main() {
int n;
printf("Enter number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter %d positive integers:\n", n);
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
printf("Original array:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
radixSort(arr, n);
printf("Sorted array:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}This interactive version allows users to input any set of positive integers. It follows the same logic as the loop-based version but lets you see the sorting process with your own data. Beginners can experiment by entering different numbers to observe how the sorting order changes. It’s a fun and practical way to understand how Radix Sort works in real programs.
Program 4: Radix Sort That Handles Negative Numbers
This program extends the basic Radix Sort to work with both negative and positive integers. It separates the numbers into two groups, sorts each, and then combines them properly.
#include <stdio.h>
#include <stdlib.h>
int getMax(int arr[], int n) {
int max = abs(arr[0]);
for (int i = 1; i < n; i++)
if (abs(arr[i]) > max)
max = abs(arr[i]);
return max;
}
void countingSort(int arr[], int n, int exp) {
int output[n];
int count[10] = {0};
for (int i = 0; i < n; i++)
count[(abs(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[(abs(arr[i]) / exp) % 10] - 1] = arr[i];
count[(abs(arr[i]) / exp) % 10]--;
}
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
void radixSort(int arr[], int n) {
int max = getMax(arr, n);
for (int exp = 1; max / exp > 0; exp *= 10)
countingSort(arr, n, exp);
}
void radixSortWithNegatives(int arr[], int n) {
int negCount = 0, posCount = 0;
for (int i = 0; i < n; i++) {
if (arr[i] < 0) negCount++;
else posCount++;
}
int negArr[negCount], posArr[posCount];
int ni = 0, pi = 0;
for (int i = 0; i < n; i++) {
if (arr[i] < 0)
negArr[ni++] = abs(arr[i]);
else
posArr[pi++] = arr[i];
}
radixSort(negArr, negCount);
radixSort(posArr, posCount);
// Reconstruct: negatives in reverse order (to maintain correct ascending order)
for (int i = 0; i < negCount; i++)
arr[i] = -negArr[negCount - 1 - i];
for (int i = 0; i < posCount; i++)
arr[negCount + i] = posArr[i];
}
int main() {
int arr[] = {170, -45, 75, -90, 802, 24, -2, 66};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
radixSortWithNegatives(arr, n);
printf("Sorted array:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}This version works perfectly for both positive and negative integers. It separates negatives and positives first. Negative numbers are converted to positive (temporarily) so that Radix Sort can process their digits normally. Then, after sorting, the negatives are flipped back and placed before the positive numbers in reverse order, ensuring the final array is sorted correctly.
This approach is not only efficient but also conceptually clean — it doesn’t modify the core Radix Sort algorithm much, it just adjusts the preprocessing and postprocessing steps.
Frequently Asked Questions (FAQ)
Here are some common questions learners often ask when exploring Radix Sort in C.
What is the main idea behind Radix Sort?
Radix Sort works by sorting numbers one digit at a time, starting from the least significant digit and moving toward the most significant digit.
Is Radix Sort faster than other sorting algorithms?
In many cases, yes. Radix Sort has a linear time complexity of O(nk), where n is the number of elements and k is the number of digits. It’s especially efficient when the number of digits is small compared to the total number of elements.
Can Radix Sort handle negative numbers?
The basic version of Radix Sort works best with non-negative integers. However, with some modifications, it can be adapted to handle negative numbers as well.
What is the difference between Radix Sort and Counting Sort?
Counting Sort is used as a subroutine inside Radix Sort. Counting Sort arranges numbers based on individual digits, while Radix Sort repeatedly applies it to each digit position to achieve a fully sorted array.
Conclusion
Radix Sort is a powerful and efficient algorithm for sorting integers, especially when dealing with large lists of numbers. Its unique digit-by-digit approach makes it faster than traditional comparison-based algorithms in many cases. For beginners learning C programming, Radix Sort is a great way to understand how numbers can be organized using mathematical logic rather than comparisons.
Whether you use loops, recursion, or user input, every version of Radix Sort teaches valuable lessons about arrays, functions, and algorithmic thinking. Keep practicing these programs, experiment with different data, and soon you’ll find sorting in C to be both easy and enjoyable — like solving a logical puzzle with clear, step-by-step rules.
