Algorithms and data structures · Intermediate

Radix sort: preserve earlier passes when sorting digits

Follow least-significant-digit passes to see why stability preserves lower-digit order and how radix and width affect cost.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Process least-significant digits first
  2. Trace a two-digit example
  3. Account for digits and radix
  4. Handle signs and variable lengths
  5. Ask Logeia about this articleCheck your understanding

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.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 10

Choose a learning path