Process least-significant digits first
Least-significant-digit radix sort represents each key using d digits in radix r and performs a stable sort on one digit at a time, starting with the least significant. After each pass, the keys are ordered by the digit suffix processed so far. This invariant makes the next pass meaningful. Fixed-width strings can be handled similarly when their alphabet has a defined order. Numeric order and character-code order are different specifications, however. The analysis also assumes that extracting a digit has the stated cost and that the chosen representation really has the expected width.
Trace a two-digit example
Sort [21,13,12] by the units digit to obtain [21,12,13]. A stable tens-digit pass then gives [12,13,21]. The records with tens digit 1 retain their units-digit order from the previous pass. If the second pass arbitrarily reorders equal tens digits, it may destroy the progress already made. The desired final ordering is lexicographic from the most significant digit downward: a higher digit decides first, and lower digits resolve ties. Stability allows the algorithm to build that structure by processing the digits in the reverse direction.
Account for digits and radix
Using stable counting sort for each digit takes O(n+r) per pass and O(d(n+r)) overall. Calling this linear in n requires treating both d and r appropriately; arbitrary-precision numbers or long strings do not have a universal constant digit count. A larger radix reduces the number of passes but enlarges the counter array and can change memory behavior. It is therefore not automatically preferable. Standard implementations use O(n+r) auxiliary space for output and counters. Representation conversion and moving complete records can add costs that are not captured by counting digit comparisons alone.
Handle signs and variable lengths
Interpreting a signed integer’s raw bits as an unsigned value usually gives the wrong numeric order across the sign boundary. A representation-specific transformation, such as adjusting the sign bit, is needed. Variable-length strings require an explicit end-of-key convention or a different design such as most-significant-digit sorting. MSD partitions by earlier digits and recursively handles groups; its implementation properties should not simply be attributed to LSD. Test empty input, repeated digits and extreme signed values, and check stable order for records with equal full keys as well as the correctness of the final sequence.