Radix Sort

Radix sort builds a complete order one digit at a time

Least-significant-digit radix sort orders numbers by one digit place at a time, starting with the ones place. For the array [170, 45, 75, 90, 802, 24, 2, 66], each value goes into a bucket numbered 0 through 9 according to its current digit. The digit at a chosen place is extracted with (value / place) % 10, using integer division.

int place = 1; // ones place
int digit = (value / place) % 10;

At place 1, the ones digits are 0, 5, 5, 0, 2, 4, 2, and 6. Put values into their buckets as you encounter them, then read the buckets from 0 through 9. Equal-digit values must leave a bucket in their arrival order, so bucket 0 contains 170 then 90, and bucket 2 contains 802 then 2.

Reading those buckets produces [170, 90, 802, 2, 24, 45, 75, 66]. This row is not numerically sorted yet. It is arranged so that the ones digit is ordered, while the arrival order inside each equal-digit group is ready to carry information into the next pass.

Every digit pass must preserve the order created by earlier passes

The next digit pass uses the tens digit of [170, 90, 802, 2, 24, 45, 75, 66]. The values reach their tens buckets in this order: bucket 0 gets 802 then 2, bucket 2 gets 24, bucket 4 gets 45, bucket 6 gets 66, bucket 7 gets 170 then 75, and bucket 9 gets 90.

Reading the tens buckets produces [802, 2, 24, 45, 66, 170, 75, 90]. Notice that 802 stays before 2 in digit-0 because they were already in that order after the ones-place pass. Likewise, 170 stays before 75 in digit-7. A pass that reverses equal-digit values can destroy the ordering established by an earlier digit, so sorting each digit is not sufficient without stability.

Missing higher digits act as zero digits

The hundreds-place pass examines [802, 2, 24, 45, 66, 170, 75, 90]. Values shorter than three digits have no written hundreds digit, so their hundreds digit acts as 0. Thus 2, 24, 45, 66, 75, and 90 enter bucket 0 in their current order, while 170 enters bucket 1 and 802 enters bucket 8.

Reading the buckets gives [2, 24, 45, 66, 75, 90, 170, 802]. The maximum value is 802, which has three digit places, so the process needs the ones, tens, and hundreds passes. Stopping after the tens pass would leave 802 before the smaller values because its tens digit is 0, even though its hundreds digit is larger.

The digit range controls the cost and the input rules

For this base-10 version, each digit pass scans the n values and distributes them among 10 buckets, then reads those buckets back. If d digit places are processed, the time is O(d * (n + 10)). For this trace, n is 8 and d is 3, so the work is O(3 * (8 + 10)), which is linear in the input size when the number of digit places is bounded.

The output array and the bucket storage require O(n + 10) extra space. Here that is O(8 + 10). The direct version described here accepts nonnegative integers. Signed values need an explicit extension, such as separating negative and nonnegative values and combining them in the correct order.