Radix Sort — Sorting

🌱 What Is Radix Sort?

Radix Sort is a non-comparative sorting algorithm — meaning it doesn’t compare numbers directly.
Instead, it sorts numbers digit by digit, starting from either the least significant digit (LSD) or the most significant digit (MSD).

Think of it like sorting a list of phone numbers:
You could first arrange them by the last digit, then by the second-last, and so on — until the whole list is perfectly ordered.

🧩 How Radix Sort Works (Step-by-Step)

Let’s understand this with an example:
We’ll sort [170, 45, 75, 90, 802, 24, 2, 66] in ascending order using LSD (Least Significant Digit) method.

Step 1: Sort by the rightmost digit (units place)

We group numbers according to their last digit:

Digit	Numbers
0	170, 90
2	802, 2
4	24
5	45, 75
6	66
8	–
9	–

After rearranging:
[170, 90, 802, 2, 24, 45, 75, 66]

Step 2: Sort by the next digit (tens place)

Now we look at the second digit from the right:

Digit	Numbers
0	802, 2
2	24
4	45
6	66
7	75
9	90
7	170

After rearranging:
[802, 2, 24, 45, 66, 75, 90, 170]

Step 3: Sort by the leftmost digit (hundreds place)

Now we sort based on the hundreds digit:

Digit	Numbers
0	2, 24, 45, 66, 75, 90
1	170
8	802

Final sorted list:
[2, 24, 45, 66, 75, 90, 170, 802]

📊 Diagram of Radix Sort

Initial List: [170, 45, 75, 90, 802, 24, 2, 66]

Pass 1 (On units digit):   [170, 90, 802, 2, 24, 45, 75, 66]
Pass 2 (On tens digit):    [802, 2, 24, 45, 66, 75, 90, 170]
Pass 3 (On hundreds digit):[2, 24, 45, 66, 75, 90, 170, 802]

Each pass brings the list closer to being fully sorted.

🧠 Why It Works

Radix Sort relies on stable sorting — meaning if two numbers have the same digit in the current position, their order stays the same as before.
That’s why we often use another algorithm like Counting Sort inside Radix Sort to handle each digit group efficiently.

💡 Real-Life Analogy

Imagine sorting a box of letters addressed to different cities.
You could first group them by the last letter of the city name,
then by the second last letter, and continue until they’re all neatly arranged.
That’s pretty much what Radix Sort does — but with digits!