A non-comparison algorithm that sorts numbers digit-by-digit, starting from the least significant digit (LSD).
We look at the last digit of each number and drop it into the matching bucket 0-9.
170->0, 90->0, 802->2, 2->2, 24->4, 45->5, 75->5, 66->6.
We gather them back from Bucket 0 to 9. The order is preserved (Stable Sort).
Now we sort by the second digit. 170->7, 02->0, 24->2...
Note: 802 has '0' in tens place. 2 is '02', so '0' tens.
Gathering back... Notice the list is getting more ordered.
Final pass. Most numbers have '0' hundreds (e.g. 45 -> 045).
Almost everyone goes to Bucket 0. 170 goes to 1. 802 goes to 8.
Gathering from 0 to 9 one last time.
The array is perfectly sorted! We did this without ever comparing two numbers directly (like 802 > 170).
O(n·k) where k is the number of digits. For fixed-size integers, this is effectively O(n) linear time!
Radix Sort breaks the O(n log n) barrier by using the structure of numbers themselves.