Non-comparative integer sorting — digit by digit, bucket by bucket
Radix Sort is a non-comparative sorting algorithm that sorts integers by processing individual digits. Instead of comparing elements directly, it distributes numbers into buckets based on each digit position, then collects them back in order.
This implementation uses LSD (Least Significant Digit) approach:
1. Start from the rightmost digit (ones place)
2. Distribute all numbers into buckets 0-9 based on current digit
3. Collect numbers from buckets in order (0→9)
4. Move to the next digit (tens, hundreds, ...)
5. Repeat until all digits are processed
The magic: after processing all digits, the array is sorted! This works because the bucket
distribution is stable — equal elements maintain their relative order.