What Is Radix Sort Algorithm?
Radix Sort is a non-comparison-based sorting algorithm that sorts elements by processing individual digits or characters instead of comparing entire values.
It works by sorting numbers digit by digit, starting from the least significant digit (LSD) to the most significant digit (MSD), or vice versa.
Radix Sort commonly uses a stable sorting algorithm such as Counting Sort to arrange elements at each digit position.
For example, consider the following array:
170, 45, 75, 90, 802, 24, 2, 66
Radix Sort processes the numbers based on:
- Units place (ones digit).
- Tens place.
- Hundreds place.
After processing all required digit positions, the array becomes:
2, 24, 45, 66, 75, 90, 170, 802
Key point: Radix Sort does not compare complete numbers. It sorts them using individual digits and a stable sorting technique.
Characteristics of Radix Sort
The important characteristics of Radix Sort are:
- It is a non-comparison-based sorting algorithm.
- It sorts elements digit by digit.
- It commonly uses Counting Sort as an intermediate sorting algorithm.
- It can achieve linear-time performance when the number of digit positions and the base are suitably bounded.
- It is a stable sorting algorithm when its intermediate sorting method is stable.
- It requires additional memory for intermediate sorting.
- It is useful for sorting integers, fixed-length strings, and structured numeric keys.
Types of Radix Sort
Radix Sort is mainly classified into two types based on the direction in which digits are processed.
1. Least Significant Digit (LSD) Radix Sort
LSD Radix Sort starts sorting from the rightmost digit (units place) and gradually moves towards the leftmost digit (most significant place).
2. Most Significant Digit (MSD) Radix Sort
MSD Radix Sort starts sorting from the leftmost digit (most significant place) and gradually processes the remaining digits.
1. Least Significant Digit (LSD) Radix Sort
LSD Radix Sort begins with the last digit of each number and processes the remaining digits from right to left.
Example of LSD:
Original Array:
170, 45, 75, 90, 802, 24, 2, 66
Pass 1: Sort by units digit
Pass 2: Sort by tens digit
Pass 3: Sort by hundreds digit
Final Sorted Array:
2, 24, 45, 66, 75, 90, 170, 802
LSD Radix Sort is commonly implemented using stable Counting Sort for each digit position.
2. Most Significant Digit (MSD) Radix Sort
MSD Radix Sort starts processing from the leftmost digit of each number.
It groups elements according to their most significant digit and then recursively sorts the individual groups using the remaining digits.
Example of MSD:
Consider:
329, 457, 657, 839, 436, 720, 355
First, group the numbers based on their hundreds digit:
| Hundreds digit | Numbers |
|---|---|
| 3 | 329, 355 |
| 4 | 457, 436 |
| 6 | 657 |
| 7 | 720 |
| 8 | 839 |
Next, sort each group using the remaining digits.
Final sorted array:
329, 355, 436, 457, 657, 720, 839
MSD Radix Sort is particularly useful in string sorting and applications where keys can be divided into groups based on their leading characters.
Radix sort working
Let’s understand the working of LSD Radix Sort using a simple example.
Consider the following array:
[170, 45, 75, 90, 802, 24, 2, 66]
We use Counting Sort to sort the elements according to each digit position.
Step 1: Find the Maximum Element
First, identify the largest number in the array.
Maximum element = 802
The maximum number contains three digits.
Therefore, we need three passes:
- First pass: Units place.
- Second pass: Tens place.
- Third pass: Hundreds place.
Step 2: Sort According to the Units Digit
Extract the units digit using:
| Number | Units digit |
|---|---|
| 170 | 0 |
| 45 | 5 |
| 75 | 5 |
| 90 | 0 |
| 802 | 2 |
| 24 | 4 |
| 2 | 2 |
| 66 | 6 |
After stable sorting based on the units digit:
[170, 90, 802, 2, 24, 45, 75, 66]
Step 3: Sort According to the Tens Digit
Now extract the tens digit using:
| Number | Tens digit |
|---|---|
| 170 | 7 |
| 90 | 9 |
| 802 | 0 |
| 2 | 0 |
| 24 | 2 |
| 45 | 4 |
| 75 | 7 |
| 66 | 6 |
After stable sorting based on the tens digit:
[802, 2, 24, 45, 66, 170, 75, 90]
Step 4: Sort According to the Hundreds Digit
Now extract the hundreds digit using:
| Number | Hundreds digit |
|---|---|
| 802 | 8 |
| 2 | 0 |
| 24 | 0 |
| 45 | 0 |
| 66 | 0 |
| 170 | 1 |
| 75 | 0 |
| 90 | 0 |
After stable sorting based on the hundreds digit:
[2, 24, 45, 66, 75, 90, 170, 802]
Final sorted array
2, 24, 45, 66, 75, 90, 170, 802
Radix Sort Algorithm
Input: An array ARR containing non-negative integers.
Output: The array sorted in ascending order.
- Start.
- Find the maximum element in the array.
- Initialize the digit position
exp = 1. - Repeat while
max / exp > 0:- Apply Counting Sort based on the current digit.
- Update the digit position by multiplying
expby 10.
- Repeat until all digit positions are processed.
- Display the sorted array.
- Stop.
Radix Sort Algorithm (Pseudocode)
RADIX_SORT(ARR, n)
1. Find MAX element in ARR
2. Set EXP = 1
3. WHILE MAX / EXP > 0
COUNTING_SORT(ARR, n, EXP)
EXP = EXP * 10
END WHILE
4. RETURN ARR
Counting Sort Pseudocode Used in Radix Sort
COUNTING_SORT(ARR, n, EXP)
1. Create OUTPUT array of size n
2. Initialize COUNT array of size 10 with zeros
3. FOR i = 0 to n-1
DIGIT = (ARR[i] / EXP) % 10
COUNT[DIGIT]++
4. FOR i = 1 to 9
COUNT[i] = COUNT[i] + COUNT[i-1]
5. FOR i = n-1 down to 0
DIGIT = (ARR[i] / EXP) % 10
OUTPUT[COUNT[DIGIT] - 1] = ARR[i]
COUNT[DIGIT]--
6. FOR i = 0 to n-1
ARR[i] = OUTPUT[i]
7. RETURN ARR
Radix Sort Program in C
The following C program implements LSD Radix Sort using Counting Sort. It accepts non-negative integers and sorts them in ascending order.
#include <stdio.h>
#include <stdlib.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, long long exp) {
int *output = malloc(n * sizeof(int));
int count[10] = {0};
if (output == NULL) {
printf("Memory allocation failed.");
exit(1);
}
// Count digit occurrences
for (int i = 0; i < n; i++) {
int digit = (arr[i] / exp) % 10;
count[digit]++;
}
// Calculate cumulative count
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// Build output array from right to left
for (int i = n - 1; i >= 0; i--) {
int digit = (arr[i] / exp) % 10;
output[count[digit] - 1] = arr[i];
count[digit]--;
}
// Copy sorted elements back
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
free(output);
}
void radixSort(int arr[], int n) {
int max = getMax(arr, n);
for (long long exp = 1; max / exp > 0; exp *= 10) {
countingSort(arr, n, exp);
}
}
int main() {
int n;
printf("Enter the number of elements: ");
scanf("%d", &n);
if (n <= 0) {
printf("Invalid array size.");
return 0;
}
int *arr = malloc(n * sizeof(int));
if (arr == NULL) {
printf("Memory allocation failed.");
return 1;
}
printf("Enter array elements:\n");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
if (arr[i] < 0) {
printf("Radix Sort implementation accepts only non-negative integers.");
free(arr);
return 1;
}
}
printf("Before sorting:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
radixSort(arr, n);
printf("\nAfter sorting:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
free(arr);
return 0;
}
Output
Enter the number of elements: 5
Enter array elements:
23 11 43 56 12
Before sorting:
23 11 43 56 12
After sorting:
11 12 23 43 56
Radix Sort Complexity
| Scenario | Complexity | Explanation |
|---|---|---|
| Best Case | O(d × (n + b)) | Each digit is processed using stable Counting Sort. |
| Average Case | O(d × (n + b)) | Every digit position requires one complete sorting pass. |
| Worst Case | O(d × (n + b)) | The number of passes depends on the maximum number of digits, not the initial arrangement. |
| Space Complexity | O(n + b) | Extra space is required for the output array and counting array. |
| Stable Sort | Yes | Maintains the relative order of elements having equal keys, provided the intermediate sorting algorithm is stable. |
| In-Place Sort | No | Standard Radix Sort implementations require additional memory. |
| Comparison-Based | No | Sorts elements based on individual digits rather than comparing complete elements. |