Radix sort for fixed-width identifiers

Least-significant-digit radix sort processes fixed-width identifiers from right to left using a stable sort at each position. Stability preserves the ordering established by less significant digits when the next digit ties. If you understand counting sort, radix sort shows how several small-key sorts can combine into a full ordering without directly comparing complete identifiers.

Use strings of exactly three ASCII decimal digits, including leading zeroes. Under this contract, lexicographic order agrees with the order of the encoded nonnegative integers. The identifiers "002" and "024" retain their width in the result. Variable-width strings, signed numbers, and locale-aware text require different rules.

Trace three passes on the same records

Start with 170, 045, 075, 090, 802, 024, 002, 066. A stable units-digit pass produces 170, 090, 802, 002, 024, 045, 075, 066. Equal units digits retain their input order: 170 stays before 090, and 802 stays before 002.

The tens-digit pass then produces 802, 002, 024, 045, 066, 170, 075, 090. For example, 170 and 075 share tens digit seven. The units pass already put 170 before 075 because zero is less than five, and stability keeps that order. Finally the hundreds pass yields 002, 024, 045, 066, 075, 090, 170, 802.

View full-size image ↗

After each pass, inspect only the suffix processed so far. The tens pass sorts the last two digits, so 802 and 002 belong together at its start even though their full numeric values are far apart. That temporary order is expected.

Implement a stable digit distribution

Ten buckets are enough for one decimal digit. Append identifiers to their digit bucket while scanning left to right, then concatenate the buckets from zero through nine. Appending preserves the order within each equal-digit bucket.

def radix_sort_ids(identifiers, width):
    if type(width) is not int or width < 1:
        raise ValueError('width must be a positive integer')
    result = list(identifiers)
    if any(not isinstance(value, str) or len(value) != width or
           any(character not in '0123456789' for character in value)
           for value in result):
        raise ValueError('expected fixed-width ASCII decimal identifiers')
    for position in range(width - 1, -1, -1):
        buckets = [[] for _ in range(10)]
        for value in result:
            buckets[ord(value[position]) - ord('0')].append(value)
        result = [value for bucket in buckets for value in bucket]
    return result

identifiers = ['170', '045', '075', '090', '802', '024', '002', '066']
assert radix_sort_ids(identifiers, 3) == [
    '002', '024', '045', '066', '075', '090', '170', '802',
]
assert radix_sort_ids([], 3) == []

Checking membership in ASCII digits is deliberate. Python’s broader digit classification can accept characters that this subtraction-based bucket mapping does not handle. A string key’s representation is part of the algorithm’s contract, so validation should match the actual indexing rule.

A production implementation may use a count array, prefix positions, and a reusable output buffer to avoid allocating many small bucket lists. The stable distribution principle remains the same. Princeton’s LSD sort and its implementation use key-indexed counting to perform those passes.

Stability carries the induction

After the units pass, identifiers are sorted by their last digit. Assume that after a pass they are sorted by their last k digits. The next pass groups them by the digit immediately before that suffix. Groups appear in ascending new-digit order. Inside an equal-digit group, stability preserves the already sorted k-digit suffix.

The result is therefore sorted by the last k + 1 digits. Once all width digits have been processed, that suffix is the full identifier, proving the final order. Every pass also preserves the set and multiplicity of input records because each identifier enters and leaves one bucket.

An unstable pass breaks the induction. Consider 12 and 11. The units pass orders them as 11 then 12. They share tens digit one, so an unstable tens pass could reverse them to 12 then 11. Every individual digit pass would still group equal digits correctly, yet the final full-key order would be wrong.

The radix and the key width are costs

For n identifiers, width w, and radix R, a counting-based pass costs O(n + R). The complete sort costs O(w(n + R)), plus input validation of O(wn). The decimal example fixes R at ten. Extra working storage is O(n + R) references or slots when buffers are reused across passes.

Calling radix sort simply “linear” usually assumes that width and radix are bounded independently of n. If identifiers grow longer, the number of passes grows too. Choosing a larger radix processes more information per pass but increases the bucket array and can change cache behavior. Those choices belong in a concrete implementation comparison.

Radix sort avoids the comparison-sorting lower bound because it inspects digits and uses them as indices. The lower bound assumes that information about order comes only from comparisons of complete keys. There is no contradiction between the two results; they count work in different operation models.

Decide what identifier order means

Leading zeroes may be significant to an external system even when numeric comparison ignores them. Do not convert identifiers to integers merely to make a sort convenient if callers need the original representation. This implementation preserves the strings and returns a new list.

For variable-length decimal strings, padding can make numeric ordering work if the width is chosen consistently and the original strings remain attached as records. For arbitrary Unicode names, digit buckets and code-point order do not reproduce a locale’s collation rules. Use a defined collation key and a suitable sorting method instead of extending this decimal example by assumption.

Test leading zeroes, repeated full identifiers, all values in one digit bucket, and differing digit positions. Reject malformed widths and non-ASCII characters explicitly. To inspect the algorithm while learning, record the result after every pass and compare only the processed suffix before checking the final full ordering.

Validate a one-use source before sorting it

Input validation itself consumes an iterator. If the code checked a generator and only afterward called list on it, the copied input would be empty. This implementation materializes the identifiers once, then validates and sorts that list. It also rejects non-string values and requires a positive built-in integer width; booleans do not count as widths here.

source = iter(['012', '002', '011'])
assert radix_sort_ids(source, 3) == ['002', '011', '012']
assert list(source) == []

for invalid_values, invalid_width in [
    (['12'], 3), (['１２３'], 3), (['12A'], 3),
    ([123], 3), ([], 0), ([], 2.5), ([], True),
]:
    try:
        radix_sort_ids(invalid_values, invalid_width)
    except ValueError:
        pass
    else:
        raise AssertionError('invalid representation was accepted')

The full-width characters in the second rejected input look like decimal digits but are not ASCII digits. Their code points would not produce bucket indices zero through nine under this mapping. The rejected numeric value is also deliberate: converting it to a string would invent a representation policy, including what to do about leading zeroes. The caller must supply that policy before invoking this particular sort.

Materializing once supports finite iterables; it does not make the algorithm a streaming sort with bounded memory independent of input size. All identifiers remain available for every digit pass. Width validation happens before consuming the source, but checking the values happens after the source is copied. A caller needing a maximum input size must enforce that separately, especially when the source could be unbounded.

Break just one tie rule to see the failure

The induction can be tested with an intentionally unstable digit pass. Reversing each digit bucket leaves the buckets in digit order while reversing records tied on that digit. The following helper is a failure demonstration, not an alternative sorting routine.

def digit_pass(values, position, reverse_ties=False):
    buckets = [[] for _ in range(10)]
    for value in values:
        buckets[ord(value[position]) - ord('0')].append(value)
    if reverse_ties:
        for bucket in buckets:
            bucket.reverse()
    return [value for bucket in buckets for value in bucket]

start = ['012', '011', '002']
units = digit_pass(start, 2)
assert units == ['011', '012', '002']
stable_tens = digit_pass(units, 1)
broken_tens = digit_pass(units, 1, reverse_ties=True)
assert stable_tens == ['002', '011', '012']
assert broken_tens == ['002', '012', '011']
assert digit_pass(broken_tens, 0) == ['002', '012', '011']

The units pass puts suffix one before suffix two. At the tens pass, 011 and 012 belong to the same digit-one bucket. Reversing that bucket destroys the units ordering. All hundreds digits are zero, so a later stable hundreds pass preserves the already broken order rather than repairing it. Correct bucket membership alone is too weak a postcondition.

View full-size image ↗

For an exercise, instrument the real implementation to retain a copy after each pass. Compare that snapshot with a stable library sort by the processed suffix of the original input. Use three-digit identifiers built from a small digit alphabet so that ties occur often, then include repeated complete identifiers as separate tagged records if you extend the interface to payloads. This tests the inductive claim at each stage, which helps identify the first broken pass instead of only reporting a wrong final list.