Example
C
#include <stdio.h>
// Helper function to get the maximum value from the array
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;
}
// Function to perform counting sort on the array according to the digit represented by exp
void countSort(int arr[], int n, int exp) {
int output[n]; // output array
int i, count[10] = {0};
// Store count of occurrences in count[]
for (i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
// Change count[i] so that count[i] now contains actual position of this digit in output[]
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
// Build the output array
for (i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
// Copy the output array to arr[], so that arr[] now contains sorted numbers
for (i = 0; i < n; i++)
arr[i] = output[i];
}
// Main function to implement radix sort
void radixSort(int arr[], int n) {
int m = getMax(arr, n); // Get the maximum number to know the number of digits
// Do counting sort for every digit. The exp is 10^i where i is the current digit number
for (int exp = 1; m / exp > 0; exp *= 10)
countSort(arr, n, exp);
}
// Driver code to test above
int main() {
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr) / sizeof(arr[0]);
radixSort(arr, n);
printf("Sorted array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
You can also try this code with Online C Compiler
Output
Sorted array: 2 24 45 66 75 90 170 802
Time & Space Complexity
Let's analyze the time & space complexity of radix sort.
Time Complexity
-
Let n be the number of elements to sort and d be the number of digits in the largest number.
-
In each iteration, radix sort processes all n elements and puts them into buckets based on the current digit. This takes O(n) time.
-
There are d iterations, one for each digit. So the total time complexity is O(d * n).
-
The value of d depends on the number of digits in the input numbers. If k is the maximum possible value, then d would be O(log k) as the number of digits is the logarithm of the number.
- Therefore, the overall time complexity of radix sort is O((n + k) * log k). It is linear in the number of elements plus the range of input values.
Space Complexity
Radix sort uses extra space for the buckets in each iteration.
The space required is O(n + k), where n is the number of elements and k is the range of input values.
In the worst case, there are n buckets (for example, if all numbers have the same digit in the current place), and each bucket may contain all n elements. So the space complexity is O(n + k).
In summary
-
Time complexity: O((n + k) * log k)
- Space complexity: O(n + k)
Radix sort is fast for integers with a small number of digits. But it can be slower than comparison-based sorting algorithms like quicksort for large numbers of digits.
Frequently Asked Questions
Is radix sort stable?
A: Yes, radix sort is a stable sorting algorithm if the underlying sorting method used for each digit is stable, like counting sort.
Can radix sort handle negative numbers?
A: Radix sort can be modified to handle negative numbers by using the most significant bit as a sign bit and then sorting based on absolute values.
Is radix sort an in-place sorting algorithm?
A: No, radix sort is not an in-place algorithm as it requires extra space for the buckets in each iteration.
Conclusion
In this article, we learned about the radix sort algorithm, which sorts integers by processing individual digits from least to most significant. We saw how the algorithm works with a proper example. We also analyzed the time complexity of O((n + k) * log k) and space complexity of O(n + k) for radix sort. Radix sort is a fast and efficient method for sorting integers when the number of digits is small.
You can refer to our guided paths on Code 360. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry.
27+ registered 
