---

📘 Radix Sort (with Running Time Analysis)

1️⃣ Introduction

Radix Sort is a non-comparison-based sorting algorithm used for sorting numbers digit by digit.

🔹 Idea

• Sort numbers based on individual digits
• Start from:
  • Least Significant Digit (LSD) → most common
  • or Most Significant Digit (MSD)

It uses a stable sorting algorithm (like Counting Sort) as a subroutine.

---

2️⃣ Working Principle

🔹 Steps (LSD Method)

1. Sort elements based on units place
2. Then sort based on tens place
3. Then hundreds place, and so on
4. Continue until all digits are processed

✔ Maintain stability at each step

---

3️⃣ Algorithm (Radix Sort)

🔹 Pseudocode

RadixSort(A, n):
   max = maximum element in A

   for exp = 1; max/exp > 0; exp = exp * 10:
       CountingSort(A, n, exp)

---

🔹 Counting Sort (for each digit)

CountingSort(A, n, exp):
   create output array
   create count[10] initialized to 0

   for i = 0 to n-1:
       index = (A[i] / exp) % 10
       count[index]++

   compute cumulative count

   for i = n-1 to 0:
       index = (A[i] / exp) % 10
       output[count[index] - 1] = A[i]
       count[index]--

   copy output to A

---

4️⃣ Example (Step-by-Step)

🔹 Given Array:

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

---

🔹 Step 1: Sort by Units Place

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

---

🔹 Step 2: Sort by Tens Place

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

---

🔹 Step 3: Sort by Hundreds Place

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

✔ Final Sorted Array

---

5️⃣ Running Time Analysis

🔹 Let:

• n = number of elements
• d = number of digits
• k = range of digits (0–9 → k = 10)

🔹 Time Complexity:

[
O(d \cdot (n + k))
]

Since k = 10 (constant):
[
O(d \cdot n)
]

---

6️⃣ Time Complexity Cases

Case	Complexity
Best Case	O(dn)
Average Case	O(dn)
Worst Case	O(dn)

✔ Same in all cases

---

7️⃣ Space Complexity

• O(n + k)
• Requires extra memory for counting sort

---

8️⃣ Characteristics of Radix Sort

✔ Non-comparison-based
✔ Stable sorting algorithm
✔ Works on integers or fixed-length keys
✔ Very fast for large datasets

---

9️⃣ Advantages

• Faster than comparison sorts for large data
• Linear time complexity (for fixed digits)
• Stable sorting

---

🔟 Disadvantages

• Extra memory required
• Not suitable for:
  • Floating-point numbers (directly)
  • Variable-length data
• Depends on digit count

---

1️⃣1️⃣ Comparison with Other Sorting Algorithms

Algorithm	Time Complexity	Type
Radix Sort	O(dn)	Non-comparison
Merge Sort	O(n log n)	Comparison
Quick Sort	O(n log n) avg	Comparison

---

🔚 Conclusion

Radix Sort is a highly efficient sorting algorithm for numbers with fixed digit lengths.

It sorts data digit by digit using a stable sorting method, achieving near-linear time complexity.

---

📌 Exam Tip

👉 Always include:

• Digit-wise sorting explanation
• Counting sort usage
• Time complexity formula
• Example

---