Radix Sort

Radix sort can order whole numbers by looking at only one digit per pass

Radix sort does not compare the whole values in [170, 45, 75, 90, 802, 24, 2, 66]. Instead, it sorts the array repeatedly by one place value, starting with the least significant digit. The ones pass uses exp = 1, the tens pass uses exp = 10, and the hundreds pass uses exp = 100.

int digit = (value / exp) % 10;

Integer division removes the digits to the right of the selected place, and % 10 keeps the digit that remains at the right. For example, when exp = 10, the expression extracts the tens digit. Each pass uses that digit as a bounded key from 0 through 9, so frequency counts and prefix positions can place the values efficiently.

The initial array is [170, 45, 75, 90, 802, 24, 2, 66]. During the ones pass, values are grouped by their ones digit. During the tens pass, they are grouped by their tens digit. During the hundreds pass, they are grouped by their hundreds digit. The word stably matters: values with the same selected digit keep the order they had before that pass.

A stable pass preserves every useful decision made by earlier passes

The ones pass puts values into digit groups while preserving their original order inside each group. The values with ones digit 0 are 170 and 90, followed by 802 and 2 with ones digit 2, then 24, 45, 75, and 66 in their own digit groups. The result is [170, 90, 802, 2, 24, 45, 75, 66].

Original order: 45, 75
Ones digits:    5,  5
After ones pass: 45, 75

The tens pass now uses the result of the ones pass as its input. It produces [802, 2, 24, 45, 66, 170, 75, 90]. Notice that 170 comes before 75 even though both have tens digit 7. Their order is inherited from the earlier ones pass: 170 had ones digit 0 and 75 had ones digit 5. The tens pass groups them by 7 without reversing that useful lower-digit order.

This is why processing from least significant digit to most significant digit works. A later pass is allowed to rearrange different current-digit groups, but inside one equal-digit group it must retain the order already created by lower places. An unstable placement could put 75 before 170, losing the information that 170 is smaller at the ones place.

Missing leading digits act as zeros, and the largest value determines the last pass

A value does not need to have as many digits as the maximum value. Treat every missing leading digit as 0 for the current place. Therefore, 2 has tens digit 0 and hundreds digit 0. In the tens pass, 802, 2, 24, 45, and 66 all begin the output according to their tens digits, with 802, 2, and 24 receiving tens digit 0 while stable order keeps 802 before 2 before 24.

The maximum value is 802, which has three digits. That means the required exp values are 1, 10, and 100. After the hundreds pass, every value has been ordered by all three relevant places. A pass with exp = 1000 would inspect a place that is 0 for every value, so it cannot change the ordering and is not needed.

After the final stable digit pass, the whole array is sorted

After the ones pass, the array is ordered by its last digit. After the tens pass, values with different tens digits are placed in the correct tens groups, while equal tens digits retain their ones-digit order. After the hundreds pass, the same rule adds the hundreds digit without destroying the order of the lower two places. The final result is [2, 24, 45, 66, 75, 90, 170, 802].

For base 10, each pass performs counting work over n values and 10 possible digit keys, then writes the n values into stable positions. If d is the number of digits in the maximum value, the total time is O(d * (n + 10)). The extra arrays for counts and stable output use O(n + 10) space.

The direct version described here assumes non-negative integers. That assumption makes every extracted digit a key from 0 through 9 and lets the maximum value determine how many passes are required. The algorithm's correctness comes from two facts together: passes run from least significant to most significant, and every pass is stable.