Understand digit-by-digit sorting, LSD and MSD Radix Sort, stable Counting Sort, complete dry run, C programming and algorithm performance with easy examples.
Suppose you have a list of roll numbers and want to arrange them from smallest to largest. In many sorting algorithms, we compare complete numbers with each other and decide which one should come first.
Radix Sort follows a different method. It does not primarily compare two complete numbers to decide their order. Instead, it processes the numbers according to their individual digits.
For example, the number 170 has three digits: 1 in the hundreds place, 7 in the tens place and 0 in the ones place.
By processing these digit positions carefully, Radix Sort can arrange the complete set of numbers.
Students often find this topic confusing because they mix up LSD and MSD, forget why stable sorting is important, or incorrectly assume that Radix Sort always takes O(n) time.
In this chapter, we will understand Radix Sort in Data Structure from the basic concept to a complete C program, using original examples, detailed calculations and exam-oriented notes.
Radix Sort is a non-comparison-based sorting algorithm that arranges keys by processing individual digits or characters. In LSD Radix Sort, digits are processed from the least significant position to the most significant position. A stable sorting method, such as Counting Sort, is used at each digit position to preserve the order established by previous passes.
What Is Radix Sort in Data Structure?

Radix Sort is a sorting technique that processes individual digit positions instead of repeatedly comparing entire numbers.
The word radix refers to the base of a number system.
For decimal numbers, the radix is 10 because the digits range from 0 to 9.
For binary numbers, the radix is 2 because only 0 and 1 are used.
Simple Radix Sort Example
Consider the values:
Each digit pass uses stable sorting to preserve earlier order.
Important Features of Radix Sort
- It processes digit positions or characters.
- It does not rely on direct pairwise comparison of complete keys.
- It can use stable Counting Sort for every digit pass.
- It is useful when keys have a suitable finite digit representation.
- Its complexity depends on the number of digits, elements and chosen radix.
- A standard LSD implementation requires additional storage.
Memory Trick: LSD Radix Sort = Sort Ones → Sort Tens → Sort Hundreds → Continue.
Understanding Digit Positions in Radix Sort
Before learning the algorithm, we must understand how individual digits are extracted.
Take the number 802. It contains three decimal digit positions.
8 hundreds, 0 tens, 2 ones
Formula to Extract a Digit
To find a particular digit of a non-negative integer, we can use integer division and remainder.
Example: Extract Digits from 802
What Happens to Smaller Numbers?
Suppose the number is 2. It does not have a written tens or hundreds digit.
During LSD sorting, missing higher digits are treated as zero.
These leading zeros are only used to understand digit positions. They do not change the number.
LSD Radix Sort vs MSD Radix Sort
Radix Sort is commonly discussed in two major forms: LSD Radix Sort and MSD Radix Sort.
1. LSD Radix Sort
LSD stands for Least Significant Digit.
This approach begins with the rightmost digit. For decimal numbers, that is the ones position.
After sorting by ones, it processes tens, hundreds and any remaining higher positions.
LSD Radix Sort requires stable ordering at each digit position so that the results of earlier passes are preserved.
2. MSD Radix Sort
MSD stands for Most Significant Digit.
This method begins with the highest significant digit position and then processes lower positions inside the appropriate groups.
MSD implementations are often described using recursive partitioning of strings or digit keys.
| Feature | LSD Radix Sort | MSD Radix Sort |
|---|---|---|
| Starting Position | Least significant digit | Most significant digit |
| Direction | Right to left | Left to right |
| Typical Method | Stable digit passes | Recursive grouping |
| Stability | Stable if every pass is stable | Depends on implementation |
| Common Use | Fixed-width or bounded integer keys | Strings and digit-prefix grouping |
Exam Tip: LSD starts from the smallest place value. MSD starts from the largest significant place value. Their implementations are not interchangeable.
How Does LSD Radix Sort Work?
The standard LSD Radix Sort process has four main steps.
Determine how many digit positions are needed.
Begin at the ones position.
Arrange numbers by the current digit.
Move to the next higher digit position.
How Digit Buckets Work
In decimal Radix Sort, each digit belongs to one of ten possible categories: 0 through 9.
We can imagine ten buckets. Numbers are grouped using the current digit while keeping the relative order within each group.
This bucket idea helps us understand the algorithm visually. The C implementation later uses stable Counting Sort to produce the same ordering.
Radix Sort Example with Complete Dry Run
Consider the array:
We will sort these values using decimal LSD Radix Sort in ascending order.
Step 1: Find the Maximum Value
The largest number is 802, which has three digits.
Therefore, we need three digit passes: ones, tens and hundreds.
Pass 1: Sort by Ones Digit
First, find the last digit of every number.
| Number | Ones Digit |
|---|---|
| 170 | 0 |
| 45 | 5 |
| 75 | 5 |
| 90 | 0 |
| 802 | 2 |
| 24 | 4 |
| 2 | 2 |
| 66 | 6 |
Ones-Digit Buckets
Now collect the groups in digit order. Values sharing the same digit stay in their original relative order.
Pass 2: Sort by Tens Digit
Take the result of Pass 1 and sort by the tens digit.
Sort these tens digits stably, keeping the previously established ones-digit order for equal tens digits.
Pass 3: Sort by Hundreds Digit
Now sort the result by the hundreds digit.
Group the six numbers having hundreds digit zero, then the number with hundreds digit 1, and finally the number with hundreds digit 8.
Radix Sort Pass-by-Pass Table
| Stage | Digit Position | Array After Pass |
|---|---|---|
| Original | — | 170, 45, 75, 90, 802, 24, 2, 66 |
| Pass 1 | Ones | 170, 90, 802, 2, 24, 45, 75, 66 |
| Pass 2 | Tens | 802, 2, 24, 45, 66, 170, 75, 90 |
| Pass 3 | Hundreds | 2, 24, 45, 66, 75, 90, 170, 802 |
2, 24, 45, 66, 75, 90, 170, 802
The maximum number has three digits, so the standard decimal LSD method completes three passes.
Important Exam Point: After the ones-digit pass, the array is not necessarily fully sorted. Do not stop until all required higher digit positions are processed.
Radix Sort Using Counting Sort
Counting Sort is commonly used inside LSD Radix Sort.
In this approach, we do not count the frequency of complete numbers.
Instead, we count how many numbers contain each possible digit at the current place value.
Steps of Stable Counting Sort
- Find the current digit of every number.
- Count the frequency of digits from 0 to 9.
- Convert the counts into cumulative counts.
- Traverse the input from right to left.
- Place every element at its correct output position.
- Copy the completed output back into the original array.
Why Must Counting Sort Be Stable?
Stability means that two values with equal sorting keys keep their previous relative order during a pass.
For example, if 45 appears before 75, both have ones digit 5.
A stable ones-digit pass keeps 45 before 75 while grouping numbers by their ones digits.
Later digit passes must preserve the ordering of previously processed lower digits whenever the current digits are equal.
Key Concept: LSD Radix Sort is correct because each digit pass is stable. Using an unstable sorting method can destroy earlier digit ordering.
Radix Sort Algorithm in Data Structure
The following pseudocode explains decimal LSD Radix Sort for non-negative integers.
LSD Radix Sort Algorithm
Algorithm RadixSort(A, n)
1. Find maximum value MAX in A
2. place = 1
3. While MAX / place > 0
StableCountingSort(A, n, place)
place = place * 10
4. Stop
Stable Counting Sort Pseudocode
1. Create count[0..9] = 0
2. Create output[0..n-1]
3. For i = 0 to n-1
digit = (A[i] / place) % 10
count[digit]++
4. For digit = 1 to 9
count[digit] += count[digit - 1]
5. For i = n-1 down to 0
digit = (A[i] / place) % 10
output[--count[digit]] = A[i]
6. Copy output into A
7. Return
Why Does the Loop Go from Right to Left?
Cumulative counts identify the ending position for each digit category.
By placing input elements from right to left and reducing the corresponding count, elements with equal digits keep their original relative order.
Important Variables in Radix Sort
| Variable | Purpose |
|---|---|
| n | Number of array elements |
| MAX | Largest input value |
| place | Current digit position |
| digit | Extracted digit from 0 to 9 |
| count | Digit frequencies and cumulative positions |
| output | Temporary array for stable sorting |
Radix Sort Time Complexity and Space Complexity
Radix Sort's performance depends on three important quantities: number of elements, digit positions and size of the digit alphabet.
Best-Case Time Complexity
The standard implementation processes every required digit position even if numbers are already sorted.
Therefore, for a fixed number of passes d, its running time follows O(d(n+b)).
Average-Case Time Complexity
Every digit pass counts, computes cumulative positions and copies the elements.
The total time remains O(d(n+b)) for the standard implementation.
Worst-Case Time Complexity
The same number of digit passes is required for an input with the same maximum digit length.
The standard LSD implementation therefore has worst-case time O(d(n+b)).
Radix Sort Time Complexity Derivation
A stable Counting Sort pass needs O(n+b) time to count frequencies, build cumulative positions and distribute elements.
If d digit positions must be processed, this work repeats d times.
When Can Radix Sort Be O(n)?
If both digit count and radix are fixed constants, such as a fixed-width integer representation with a chosen constant base, the expression becomes O(n).
But if the number of digits increases with the input range, we must include d in the analysis.
Radix Sort Space Complexity
The counting-based algorithm uses an output array of size n and a counting array of size b.
For base 10, b is constant, so the space complexity becomes O(n).
| Case | Complexity | Condition |
|---|---|---|
| Best Time | O(d(n+b)) | Standard full-digit processing |
| Average Time | O(d(n+b)) | Stable digit passes |
| Worst Time | O(d(n+b)) | All d digit positions processed |
| Auxiliary Space | O(n+b) | Output and count arrays |
| Base-10 Space | O(n) | Fixed ten digit categories |
Important: The common claim that Radix Sort always takes O(n) time is incomplete. Its performance depends on the digit length and the radix.
Interactive Radix Sort Visualizer
The following Radix Sort visualizer shows how each number enters its current digit bucket.
You can follow the ones, tens, hundreds and higher digit positions one step at a time.
Digit Sorting Workshop
This simulator uses base-10 LSD Radix Sort with stable bucket collection.
Enter 3 to 10 non-negative integers between 0 and 9999.
Ready to start.
Practice Task: Try the default eight values. Then enter 91, 12, 41, 22, 11 and observe how stability preserves lower-digit ordering across passes.
Radix Sort Program in C with Output
The following C program implements LSD Radix Sort for non-negative integers.
It uses stable Counting Sort at every digit position and displays the complete array after each pass.
The program accepts up to 100 numbers, checks basic input validity and safely handles all-zero input.
Complete Radix Sort C Program
#include <stdio.h>
#include <limits.h>
#define MAX 100
#define BASE 10
void printArray(const int a[], int n) {
for (int i = 0; i < n; ++i) {
printf(
"%d%s",
a[i],
i == n - 1 ? "\n" : " "
);
}
}
void stableDigitSort(
int a[],
int n,
long long place,
int output[]
) {
int counts[BASE] = {0};
/* Count digit frequencies */
for (int i = 0; i < n; ++i) {
int digit =
(int)((a[i] / place) % BASE);
++counts[digit];
}
/* Build cumulative counts */
for (int digit = 1;
digit < BASE;
++digit) {
counts[digit] += counts[digit - 1];
}
/* Stable placement from right to left */
for (int i = n - 1; i >= 0; --i) {
int digit =
(int)((a[i] / place) % BASE);
output[--counts[digit]] = a[i];
}
/* Copy output back into the array */
for (int i = 0; i < n; ++i) {
a[i] = output[i];
}
}
int main(void) {
int a[MAX];
int output[MAX];
int n;
int max = 0;
int passes = 0;
printf(
"Enter number of elements (1-100): "
);
if (
scanf("%d", &n) != 1 ||
n < 1 ||
n > MAX
) {
puts("Invalid array size.");
return 1;
}
printf(
"Enter %d non-negative integers: ",
n
);
for (int i = 0; i < n; ++i) {
if (
scanf("%d", &a[i]) != 1 ||
a[i] < 0
) {
puts(
"Only non-negative integers "
"are supported."
);
return 1;
}
if (a[i] > max) {
max = a[i];
}
}
/* Process digits from ones onward */
for (
long long place = 1;
max / place > 0;
place *= BASE
) {
stableDigitSort(
a,
n,
place,
output
);
++passes;
printf(
"After place %lld: ",
place
);
printArray(a, n);
}
if (max == 0) {
puts(
"All values are zero; "
"no digit passes required."
);
}
printf("Sorted array: ");
printArray(a, n);
printf(
"Digit passes: %d\n",
passes
);
return 0;
}
Sample Input
Enter number of elements (1-100): 8
Enter 8 non-negative integers:
170 45 75 90 802 24 2 66
Output of Radix Sort C Program
After place 1: 170 90 802 2 24 45 75 66
After place 10: 802 2 24 45 66 170 75 90
After place 100: 2 24 45 66 75 90 170 802
Sorted array: 2 24 45 66 75 90 170 802
Digit passes: 3
Explanation of the C Program
1. Read the Array
The main function accepts the number of elements and reads non-negative integer values.
2. Find the Maximum Value
The variable max stores the largest input value. Its digit count determines how many passes are needed.
3. Select the Current Digit
The variable place starts at 1, representing the ones position.
It becomes 10, 100, 1000 and so on while additional digit positions remain.
4. Count Digit Frequencies
The counts array stores how many values belong to every digit group.
5. Calculate Cumulative Counts
Cumulative counts are used to calculate positions inside the temporary output.
6. Preserve Stable Ordering
The input array is traversed from right to left during placement.
This preserves the relative ordering of values with equal current digits.
7. Copy the Sorted Pass
After placing every value into output, the temporary values are copied back into the input array.
8. Display the Result
The program prints the array after every digit pass, then shows the final result and number of passes.
Program Verification: This implementation was compiled successfully with GCC using the C11 standard. The sample output, repeated values, zero values, different digit lengths and large positive integer inputs were checked.
How to Run Radix Sort in VS Code
- Open VS Code with GCC installed.
-
Create a file named
radix_sort.c. - Paste the complete C program.
- Open the terminal in VS Code.
- Compile the program using GCC.
- Run the executable and enter your values.
gcc -std=c11 -Wall -Wextra radix_sort.c -o radix_sort
In Windows PowerShell:
.\radix_sort.exe
Can Radix Sort Handle Negative Numbers?
Radix Sort can be adapted to handle negative integers, but the simple decimal LSD program shown above supports non-negative integers only.
One possible extension is to separate negative and non-negative numbers. Negative numbers can be arranged according to absolute magnitude and then placed before non-negative numbers in the correct order.
Such an implementation must also handle the minimum representable integer safely.
Another approach processes fixed-width signed integer bits using an appropriate ordering transformation.
Important: Do not enter negative values into the C program in this chapter. It deliberately rejects them rather than giving incorrect sorting results.
Radix Sort vs Counting Sort vs Quick Sort
Radix Sort and Counting Sort are non-comparison-based sorting techniques.
Quick Sort is a comparison-based sorting algorithm that partitions values around pivots.
| Feature | Radix Sort | Counting Sort | Quick Sort |
|---|---|---|---|
| Method | Sort digit positions | Count key frequencies | Pivot partitioning |
| Comparison-Based? | No | No | Yes |
| Typical Time | O(d(n+b)) | O(n+k) | O(n log n) average |
| Typical Extra Space | O(n+b) | O(n+k) | O(log n) expected stack |
| Stable? | LSD with stable passes | Stable implementation available | Normally not stable |
| Best Suited For | Suitable digit keys | Small key range | General-purpose array sorting |
Radix Sort vs Counting Sort
Counting Sort directly counts the occurrences of keys from a limited range.
Radix Sort processes individual digits and can use Counting Sort as a subroutine.
A major difference is that Counting Sort may require a counting array related to the complete key range.
Radix Sort instead works with the smaller digit alphabet during each pass.
Radix Sort vs Quick Sort
Quick Sort compares values against pivots and recursively partitions the array.
Radix Sort processes digit positions without direct complete-key comparisons.
Radix Sort can be efficient for suitable fixed-width keys, but it also requires additional memory in its standard form.
Advantages, Disadvantages and Applications of Radix Sort
Advantages of Radix Sort
- Avoids repeated comparisons of complete keys.
- Can perform well for suitable fixed-width integer or character keys.
- Supports stable sorting with stable digit passes.
- Provides predictable per-digit work for a chosen radix.
- Can be adapted to different digit bases.
Disadvantages of Radix Sort
- Requires additional output storage in the standard approach.
- Performance depends on key length and radix.
- Signed integers need special handling.
- Stable per-digit sorting is essential for LSD correctness.
- It may be unsuitable for complex keys without a useful digit representation.
Applications of Radix Sort
Radix-based methods are useful when records contain integer keys, fixed-length identifiers or strings that can be represented using a suitable finite alphabet.
Practical implementations may use digits, bytes or groups of bits instead of individual decimal digits.
Common Mistakes in Radix Sort
| Mistake | Correct Explanation |
|---|---|
| Starting LSD with the hundreds digit | LSD begins at the least significant digit. |
| Using unstable sorting on each digit | Use stable digit ordering to preserve previous passes. |
| Ignoring shorter numbers | Missing higher digits are treated as zero. |
| Writing Radix Sort always takes O(n) | Use O(d(n+b)) for the standard analysis. |
| Claiming O(1) auxiliary space | Standard Counting Sort-based LSD Radix Sort uses O(n+b). |
| Processing only the first digit | Continue until all required positions are processed. |
| Using the non-negative version for signed input | Handle negative values separately or use an appropriate signed-key representation. |
Why Does Stability Matter So Much?
Suppose numbers are correctly grouped by ones digit.
If a later tens-digit pass unnecessarily changes the order of values with equal tens digits, the earlier ones-digit ordering can be lost.
This is why stability is a fundamental property of the standard LSD algorithm.
Important Radix Sort Questions and Answers
These original exam-style questions are useful for BCA, MCA and university practical preparation.
1. Define Radix Sort.
Radix Sort is a non-comparison-based sorting algorithm that arranges values by processing individual digits or characters.
2. What Is LSD in Radix Sort?
LSD stands for Least Significant Digit. It begins sorting from the rightmost digit and continues towards higher place values.
3. What Is MSD Radix Sort?
MSD Radix Sort processes the most significant digit first and then handles lower digit positions within the required groups.
4. Why Is Stable Sorting Required?
Stable sorting preserves the previously established lower-digit order when current digit values are equal.
5. Explain Radix Sort with an Example.
Radix Sort processes numbers according to digit positions.
In LSD Radix Sort, values are sorted stably by ones, then tens, then hundreds, and so on.
For example, 45, 12, 31, 24 becomes 31, 12, 24, 45 after the ones-digit pass.
After the tens-digit pass, the final sorted result is 12, 24, 31, 45.
6. Differentiate LSD and MSD Radix Sort.
LSD starts with the least significant digit and processes higher positions using stable digit passes.
MSD begins with the most significant digit and commonly processes grouped subproblems recursively.
7. Explain Radix Sort Algorithm and Complexity.
Radix Sort is a non-comparison-based sorting algorithm that arranges keys through digit processing.
In the standard decimal LSD method, we first find the maximum value to determine the required digit count.
Each digit position is then processed with a stable sorting algorithm such as Counting Sort.
The process starts from ones, then tens, hundreds and higher positions.
For n elements, d digit positions and radix b, stable Counting Sort takes O(n+b) per digit.
Therefore, the total time complexity is O(d(n+b)).
Its standard auxiliary space is O(n+b) because of temporary output and counting arrays.
The algorithm is stable when every digit pass is stable.
Radix Sort Practice Questions and MCQs
Question 1: Sort 21, 13, 42, 11 Using LSD Radix Sort.
Show Complete Solution
Original: 21, 13, 42, 11.
Ones-digit order: 21, 11, 42, 13.
Tens-digit order: 11, 13, 21, 42.
Final: 11, 13, 21, 42.
Question 2: What Does LSD Mean?
A. Largest Significant Digit
B. Least Significant Digit
C. Linear Sorting Digit
D. Last Sorted Data
Show Answer
B. Least Significant Digit. It refers to the rightmost digit in a positional number representation.
Question 3: Which Property Is Important for LSD Digit Sorting?
A. Recursion only
B. Stability
C. Binary search
D. Heap ordering
Show Answer
B. Stability. Stable passes preserve previously established lower-digit order.
Question 4: How Many Decimal Digit Passes Are Needed for 9865?
Show Calculation
The number 9865 contains four decimal digits.
Therefore, a full LSD sort with this maximum needs four passes: ones, tens, hundreds and thousands.
Question 5: Is Radix Sort Comparison-Based?
Show Answer
No. Standard Radix Sort processes digit categories rather than relying on pairwise comparisons of complete keys.
FAQs About Radix Sort in Data Structure
What is Radix Sort in simple words?
Radix Sort arranges numbers or keys by processing their digit or character positions.
What is the time complexity of Radix Sort?
Standard LSD Radix Sort using stable Counting Sort takes O(d(n+b)) time for d digit positions and radix b.
What is the space complexity of Radix Sort?
The standard Counting Sort-based implementation uses O(n+b) auxiliary space.
Is Radix Sort stable?
LSD Radix Sort is stable when every digit pass uses a stable sorting method.
What is the difference between LSD and MSD?
LSD begins with the least significant digit, while MSD begins with the most significant digit.
Why is Counting Sort used in Radix Sort?
Counting Sort efficiently arranges values by digit categories and can preserve stable ordering.
Can Radix Sort handle negative numbers?
Yes, using an appropriate modified implementation. The introductory C program in this chapter accepts only non-negative integers.
Is Radix Sort always O(n)?
No. Its general digit-pass time depends on d, n and b. When digit count and radix are fixed constants, the bound simplifies to O(n).
Radix Sort Quick Revision Notes
Memory Trick: Find Maximum → Start at Ones → Stable Sort → Move to Tens → Continue.
Conclusion
Radix Sort in Data Structure becomes easier once you understand digit positions and stable ordering.
Instead of repeatedly comparing complete numbers, the standard LSD method processes digits from the least significant to the most significant position.
Stable Counting Sort keeps the results of earlier passes in the correct order.
Its standard time complexity is O(d(n+b)), while auxiliary space complexity is O(n+b).
For semester examinations, practise a complete digit-by-digit dry run, understand the role of stability, write the C program and remember the difference between LSD and MSD.
Chapter 49 — Completed
