DSA Radix Sort

🔢 DSA Radix Sort – Complete Beginner Guide

(Concept • Manual Run-Through • Algorithm • Code • Time Complexity)

Radix Sort is a non-comparison based sorting algorithm that sorts numbers digit by digit.
It is especially efficient when sorting large lists of integers with a limited number of digits.

1️⃣ What is Radix Sort?

Radix Sort:

Sorts numbers digit-wise (units, tens, hundreds…)
Uses a stable sub-sorting algorithm (usually Counting Sort)
Does not compare elements directly

Most common version: LSD Radix Sort (Least Significant Digit first)

2️⃣ Simple Idea (One Line)

Sort by each digit from right to left using a stable sort

3️⃣ When to Use Radix Sort?

✔ Sorting large number of integers
✔ Numbers have limited digits
✔ Keys like phone numbers, IDs, zip codes

❌ Not suitable for:

Floating-point numbers (without modification)
Very large digit lengths
Mixed data types

4️⃣ Radix Sort – Manual Run-Through

Given Array

Step 1: Sort by Units Digit

After stable sort:

Step 2: Sort by Tens Digit

After stable sort:

Step 3: Sort by Hundreds Digit

After stable sort:

Final Sorted Array

5️⃣ How Radix Sort Works (Steps)

Find the maximum number to know the number of digits
Start from least significant digit (LSD)
Use stable Counting Sort for the current digit
Move to the next digit
Repeat until all digits are processed

6️⃣ Pseudocode

7️⃣ Radix Sort Implementation (C++)

#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 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--) {
int idx = (arr[i] / exp) % 10;
output[count[idx] - 1] = arr[i];
count[idx]--;
}

for(int i = 0; i < n; i++)
arr[i] = output[i];
}

void radixSort(int arr[], int n) {
int m = getMax(arr, n);
for(int exp = 1; m / exp > 0; exp *= 10)
countingSort(arr, n, exp);
}

int main() {
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = 8;

radixSort(arr, n);

for(int i = 0; i < n; i++)
cout << arr[i] << " ";

return 0;
}

#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 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--) {

int idx = (arr[i] / exp) % 10;

output[count[idx] - 1] = arr[i];

count[idx]--;

}

for(int i = 0; i < n; i++)

arr[i] = output[i];

}

void radixSort(int arr[], int n) {

int m = getMax(arr, n);

for(int exp = 1; m / exp > 0; exp *= 10)

countingSort(arr, n, exp);

}

int main() {

int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};

int n = 8;

radixSort(arr, n);

for(int i = 0; i < n; i++)

cout << arr[i] << " ";

return 0;

}

Output

8️⃣ Time Complexity of Radix Sort

Let:

n = number of elements
d = number of digits
k = base (10 for decimal numbers)

⏱ Time Complexity

Since k = 10, it is usually written as:

If number of digits is small → Radix Sort is very fast

9️⃣ Space Complexity

Metric	Value
Extra Space	O(n + k)
Reason	Output + count array

🔟 Advantages of Radix Sort

✔ Linear time for fixed digit length
✔ Very fast for integers
✔ Stable sorting
✔ No comparisons

1️⃣1️⃣ Disadvantages of Radix Sort

❌ Extra memory required
❌ Only for integers / strings
❌ Performance depends on digit count

1️⃣2️⃣ Radix Sort vs Counting Sort

Feature	Radix Sort	Counting Sort
Sorting basis	Digits	Values
Range issue	Avoided	Problematic
Stability	Required	Optional
Use case	Large numbers	Small range

Exam / Interview Questions (Radix Sort)

Q1. Is Radix Sort comparison based?
👉 No

Q2. Why must sub-sort be stable?
👉 To preserve digit order

Q3. Best time complexity of Radix Sort?
👉 O(d × n)

Q4. Where is Radix Sort used?
👉 Sorting IDs, phone numbers, zip codes

Final Summary

✔ Radix Sort sorts digit by digit
✔ Uses Counting Sort internally
✔ Stable and fast
✔ Time complexity: O(d × n)
✔ Suitable for large integer datasets
✔ Important non-comparison sorting algorithm

DSA Radix Sort

🔢 DSA Radix Sort – Complete Beginner Guide

(Concept • Manual Run-Through • Algorithm • Code • Time Complexity)

1️⃣ What is Radix Sort?

2️⃣ Simple Idea (One Line)

3️⃣ When to Use Radix Sort?

4️⃣ Radix Sort – Manual Run-Through

Given Array

Step 1: Sort by Units Digit

Step 2: Sort by Tens Digit

Step 3: Sort by Hundreds Digit

Final Sorted Array

5️⃣ How Radix Sort Works (Steps)

6️⃣ Pseudocode

7️⃣ Radix Sort Implementation (C++)

Output

8️⃣ Time Complexity of Radix Sort

⏱ Time Complexity

9️⃣ Space Complexity

🔟 Advantages of Radix Sort

1️⃣1️⃣ Disadvantages of Radix Sort

1️⃣2️⃣ Radix Sort vs Counting Sort

Exam / Interview Questions (Radix Sort)

Final Summary

You may also like...

DSA Tutorial

Arrays

Linked Lists

Stacks & Queues

Hash Tables

Trees

Graphs

Shortest Path

DSA Radix Sort

🔢 DSA Radix Sort – Complete Beginner Guide

(Concept • Manual Run-Through • Algorithm • Code • Time Complexity)

1️⃣ What is Radix Sort?

2️⃣ Simple Idea (One Line)

3️⃣ When to Use Radix Sort?

4️⃣ Radix Sort – Manual Run-Through

Given Array

Step 1: Sort by Units Digit

Step 2: Sort by Tens Digit

Step 3: Sort by Hundreds Digit

Final Sorted Array

5️⃣ How Radix Sort Works (Steps)

6️⃣ Pseudocode

7️⃣ Radix Sort Implementation (C++)

Output

8️⃣ Time Complexity of Radix Sort

⏱ Time Complexity

9️⃣ Space Complexity

🔟 Advantages of Radix Sort

1️⃣1️⃣ Disadvantages of Radix Sort

1️⃣2️⃣ Radix Sort vs Counting Sort

Exam / Interview Questions (Radix Sort)

Final Summary

You may also like...

DSA Quick Sort

DSA Merge Sort

DSA Selection Sort

DSA Tutorial

Arrays

Linked Lists

Stacks & Queues

Hash Tables

Trees

Graphs

Shortest Path