Radix Sort Algorithm and Bucket Distribution

Radix Sort ek non-comparison based linear time sorting algorithm hai jo integers ko digit-by-digit sort karta hai. Yeh Counting Sort ki range limitation (large k problem) ko overcome karta hai by breaking large numbers into individual digits.

LSD vs MSD Radix Sort

• LSD (Least Significant Digit): Pehle unit place (1s) digit se sorting start hoti hai, fir tens place (10s), fir hundreds place (100s), and so on. Yeh sabse popular standard approach hai.
• MSD (Most Significant Digit): Sabse higher order digit se divide-and-conquer bucket partitioning hoti hai.

Initial Array: [ 170, 045, 075, 090, 802, 024, 002, 066 ]

Pass 1 (Sort by Unit Place Digit):
17[0], 09[0] -> 80[2], 00[2] -> 02[4] -> 04[5], 07[5] -> 06[6]
Result: [ 170, 090, 802, 002, 024, 045, 075, 066 ]

Pass 2 (Sort by Tens Place Digit):
8[0]2, 0[0]2 -> 0[2]4 -> 0[4]5 -> 0[6]6 -> 1[7]0, 0[7]5 -> 0[9]0
Result: [ 802, 002, 024, 045, 066, 170, 075, 090 ]

Pass 3 (Sort by Hundreds Place Digit):
[0]02, [0]24, [0]45, [0]66, [0]75, [0]90 -> [1]70 -> [8]02
Result: [ 002, 024, 045, 066, 075, 090, 170, 802 ] -> Fully Sorted!

Why Subroutine Must Be Stable?

Radix sort tabhi correctly kaam karta hai jab har digit pass par use hone wala sorting algorithm Stable ho (usually Counting Sort use hota hai). Agar stability toot jaye, toh pichhle digits ka established sorting order disrupt ho jayega.

Complexity Analysis

• Time Complexity: O(d * (n + b)) jahan d maximum number of digits hai aur b base of numbers (decimal system me b = 10) hai. Agar d constant ho, toh time complexity linear O(n) ban jati hai.
• Space Complexity: O(n + b) auxiliary memory.
• Stability: Stable sorting algorithm.

Agli post me hum start karenge DSA Part-3: Linked Lists & Applications, jisme pehla topic hoga Singly Linked List: Concept and Memory Allocation.