Summary

Radix Sort is a non-comparative integer sorting algorithm that avoids direct element-to-element comparisons. Instead, it distributes elements into "buckets" based on their individual digits. The Least Significant Digit (LSD) variant processes the numbers starting from the units place, then the tens, then the hundreds, and so on. Crucially, it uses a stable sorting subroutine (typically Counting Sort) for each digit pass. This ensures that when sorting by the tens digit, the ordering established by the units digit is preserved.

How it Works

• Find Maximum: Determine the largest number in the array to calculate the number of digits ($d$) required for processing.

• Iterate Digits: Start with the least significant digit (units place, $10^0$).

• Frequency Count: For the current digit, count the frequency of occurrences (0-9) using a bucket array.

• Prefix Sums: Transform the count array to determine the exact starting positions for each digit value in the output.

• Placement: Traverse the array backwards (to maintain stability) and place each element into its calculated position based on the current digit.

• Repeat: Move to the next significant digit ($10^1, 10^2, ...$) and repeat the process until the most significant digit of the largest number is handled.