DSA Radix Sort

DSA Tutorial

🔢 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

[170, 45, 75, 90, 802, 24, 2, 66]

 Step 1: Sort by Units Digit

Digits: 0,5,5,0,2,4,2,6

After stable sort:

[170, 90, 802, 2, 24, 45, 75, 66]

Step 2: Sort by Tens Digit

Digits: 7,9,0,0,2,4,7,6

After stable sort:

[802, 2, 24, 45, 66, 170, 75, 90]

 Step 3: Sort by Hundreds Digit

Digits: 8,0,0,0,0,1,0,0

After stable sort:

[2, 24, 45, 66, 75, 90, 170, 802]

 Final Sorted Array

[2, 24, 45, 66, 75, 90, 170, 802]

5️⃣ How Radix Sort Works (Steps)

  1. Find the maximum number to know the number of digits

  2. Start from least significant digit (LSD)

  3. Use stable Counting Sort for the current digit

  4. Move to the next digit

  5. Repeat until all digits are processed

6️⃣ Pseudocode

find max number
for digit = 1, 10, 100, ...
apply counting sort based on digit

7️⃣ Radix Sort Implementation (C++)


 

Output

2 24 45 66 75 90 170 802

8️⃣ Time Complexity of Radix Sort

Let:

  • n = number of elements

  • d = number of digits

  • k = base (10 for decimal numbers)

⏱ Time Complexity

O(d × (n + k))

Since k = 10, it is usually written as:

O(d × n)

 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

You may also like...