Radix sort for linear-time integer sorting

Radix sort is a family of sorting algorithms that orders integers by processing their digits or fixed-width parts. Unlike comparison-based methods such as quicksort, heapsort, and mergesort, it does not decide whether one complete value is smaller by repeatedly comparing pairs. Instead, it distributes values into buckets according to individual digits, then rebuilds the sequence in a carefully chosen order.

This approach can run in linear time when the number of digits is bounded or grows slowly relative to the input size. It is particularly useful for non-negative integers, IDs, timestamps, postcodes, and other values with a predictable representation. Understanding its stable sorting requirement, memory use, handling of negative numbers, and choice of base is essential before using it in production Python or C code.

How digit-based sorting works

The most common version is least significant digit first, usually called LSD radix sort. It starts with the units digit, then sorts by the tens digit, hundreds digit, and so on. Each pass must be stable: values with the same current digit must retain the order produced by the previous pass.

Consider the values 329, 457, 657, 839, 436, 720, and 355. The first pass groups them by units digit. The second pass groups the result by tens digit, preserving the order within equal tens digits. After the final pass over the hundreds digit, the entire sequence is sorted. A stable counting sort is often used for each digit because its running time is linear in the number of values plus the number of possible digit values.

The key invariant is that after processing the position at place value (10^k), the array is sorted according to its last (k+1) digits. Once every position in the largest number has been processed, numerical order follows. LSD radix sort is straightforward to implement, while most-significant digit first radix sort can divide the input recursively and is sometimes more suitable for strings or variable-length keys.

A decimal implementation usually extracts a digit with integer arithmetic:

digit = (value // place) % base

The variable place begins at 1 and is multiplied by the base after every pass. With base 10, the passes examine units, tens, hundreds, and so forth. A larger base reduces the number of passes but increases the number of buckets and the temporary bookkeeping required by each pass.

Complexity and the meaning of linear time

Let (n) be the number of values, (d) the number of digits in the largest value, and (b) the radix or base. If counting sort processes each digit in (O(n+b)) time, the full cost is:

[ O(d(n+b)) ]

For a fixed-width integer type, both (d) and (b) can be treated as constants. Under that assumption, radix sort is (O(n)). This is the sense in which it sorts integers linearly. For arbitrary-precision integers, however, the number of machine words or digits is part of the input size, so the claim requires more care.

The auxiliary space is generally (O(n+b)). A stable counting pass needs an output array of length (n), along with counts or bucket positions. An in-place digit distribution is possible, but it is more complicated and can sacrifice stability or clarity. Radix sort therefore trades extra memory for predictable performance.

Algorithm	Typical time	Extra space	Stable by default	Useful conditions
Radix sort	(O(d(n+b)))	(O(n+b))	Yes, with stable passes	Integers with bounded digits
Counting sort	(O(n+k))	(O(n+k))	Can be stable	Small value range (k)
Quicksort	Average (O(n\log n))	(O(\log n)) average	No	General in-memory sorting
Mergesort	(O(n\log n))	(O(n))	Yes	Stable general-purpose sorting
Heapsort	(O(n\log n))	(O(1))	No	Guaranteed time with low extra memory

The linear-time advantage can disappear when integers contain many digits, the chosen base is poorly matched to the hardware, or the input is small enough that ordinary library sorting has lower overhead. Production programs should benchmark realistic data rather than selecting radix sort solely because its asymptotic bound looks better.

Implementing LSD radix sort in Python

A practical implementation first handles the empty list and determines the largest value. It then performs stable counting sort for each digit position. The following version assumes all values are non-negative integers:

def radix_sort(values):
    if not values:
        return []

    result = values[:]
    largest = max(result)
    place = 1
    base = 10

    while largest // place > 0:
        counts = [0] * base

        for value in result:
            digit = (value // place) % base
            counts[digit] += 1

        for digit in range(1, base):
            counts[digit] += counts[digit - 1]

        output = [0] * len(result)

        for value in reversed(result):
            digit = (value // place) % base
            counts[digit] -= 1
            output[counts[digit]] = value

        result = output
        place *= base

    return result

The reverse traversal in the final loop is important. It places equal digits into the output in their previous order, making the pass stable. If the loop travelled from left to right while using the same cumulative-count arrangement, equal-digit items could be reversed and later passes might produce an incorrect final order.

For a version that modifies a list in place, copy the sorted output back with values[:] = result. Python’s built-in sorted() will usually be faster for ordinary application data because it is highly optimised and handles arbitrary comparable objects. Radix sort is valuable when the data has a clear integer representation and the algorithm’s characteristics matter more than using the standard library.

This same structure maps neatly to C arrays: allocate a temporary output array, use an integer count array for the selected base, and repeat until the largest remaining place is zero. In systems programming, selecting base 256 can process one byte per pass, though the memory layout and cache behaviour should be measured rather than assumed.

Negative values, bases, and practical data

The basic algorithm does not naturally order negative and non-negative integers together because digit extraction is normally defined for values greater than or equal to zero. A common solution is to split the input into negative and non-negative values. Sort the absolute values of the negative numbers, reverse that sorted result, negate the values again, and concatenate it with the sorted non-negative section.

Another approach transforms signed integers so that their bit patterns preserve numerical order. For fixed-width two’s-complement values, flipping the sign bit maps the signed range into an unsigned range. This can make a byte-wise radix sort efficient, although the transformation must match the integer width and language representation.

The base is a design decision. Base 10 is easy to explain and often adequate for educational code. Base 2 processes one bit per pass and needs few buckets, while base 256 processes one byte per pass and is common for fixed-width binary keys. A larger base generally means fewer passes but more count storage and potentially worse cache use.

Radix sort also works well for structured keys. An Australian postcode is a four-digit value, so a fixed number of decimal passes is sufficient, although leading zeroes must be preserved if the postcode is stored as text. Similarly, integer timestamps or order identifiers in a Melbourne delivery system can be sorted efficiently when their format and width are known. Treating an identifier as a number is appropriate only when its numeric ordering has meaning; customer codes with leading zeroes may need lexicographic string sorting instead.

Choosing radix sort in real systems

Radix sort is a strong candidate when a program repeatedly sorts millions of bounded, fixed-width integers. Examples include event times, pixel channels, database keys, packet fields, and large collections of Australian transaction IDs. It can provide predictable performance and avoid the comparison overhead of general-purpose sorting, especially in low-level code where memory allocation and data representation are tightly controlled.

The surrounding application still determines whether the algorithm is suitable. An online retailer serving customers in Sydney, Perth, and regional towns may sort order records by a numeric internal key, but it should not use radix order for names, addresses, or formatted dates without defining the desired semantics. Everyday values such as phone numbers, postcodes, and bank references often contain leading zeroes or punctuation, which means their textual representation can be more important than their apparent integer value.

Data handling also matters. Under Australia’s Privacy Act 1988 and the Australian Privacy Principles, personal information should be handled carefully, even when a sorting operation itself is harmless. Avoid exposing real customer identifiers in test data, and avoid logging complete records merely to inspect sorting behaviour. A synthetic dataset with the same digit distribution is usually enough for benchmarking.

Radix sort is one tool within a broader programming toolkit. Readers comparing it with divide-and-conquer methods can explore these algorithm explanations, while developers building a browser-based visual demonstration may find related web development tutorials useful. In either setting, tests should verify sorted order, duplicates, empty input, already sorted data, reverse-sorted data, very large values, and mixtures of negative and non-negative integers.

A reliable test oracle is the language’s standard sorting function. Generate random integer arrays, run both implementations, and compare their outputs. This catches errors in cumulative counts, digit extraction, stability, and negative-number handling. It also reveals when radix sort’s theoretical advantage is outweighed by allocation costs or a small input size.

The central lesson is that radix sort achieves linear behaviour by exploiting the representation of integers. Its performance depends on digit count, radix, memory bandwidth, and stable distribution passes. When those conditions fit the data, it can outperform comparison sorting; when they do not, a mature library sort remains the safer general-purpose choice.