Abstract flowing gradient in deep indigo and blue tones, smooth and luminous, evoking a modern digital learning atmosphere

Computer Science and programming articles. We do not sell courses.

Sorting integers at speed with the radix sort algorithm

Radix sort is one of those algorithms that quietly outperforms the classics. It is not taught alongside bubble or merge sort in introductory computing classes, yet it powers the sorting routines in databases, language runtimes and high-throughput pipelines. Unlike comparison-based algorithms, which are bound by an O(n log n) lower limit, radix sort slices integers into pieces and sorts each piece independently. The result is linear-time ordering for fixed-width integer keys, something that comparison sorts simply cannot match.

For developers in Australia, the appeal is tangible. Teams at fintech firms in Barangaroo, search platforms in Carlton and logistics startups in Fortitude Valley frequently process millions of records every hour. Sorting those records by ID, transaction timestamp or session counter can become a real bottleneck. Reaching for radix sort, often implemented as a low-level routine, can turn a sluggish batch job into one that finishes before morning tea.

The core idea behind radix sort

The algorithm works by treating each integer as a sequence of digits. In its most common form, the least significant digit variant, the routine sorts the input array by its ones digit, then by tens, then by hundreds, and so on. After enough passes, the array is sorted by the whole integer. Stability is essential here, because digits are processed one position at a time and earlier passes must preserve order for later passes to work.

Each pass is essentially a stable counting sort restricted to a small range of digit values. For base-10 that range is 0 to 9, for base-256 it is 0 to 255. Smaller digit ranges mean the inner counting array stays tiny, which keeps cache behaviour friendly. It is a clever trick: split the problem into many tiny sorts rather than one big one.

LSD versus MSD variants

The least significant digit form is the most widely taught and the easiest to implement. It sweeps from the smallest place value to the largest and is naturally stable when paired with counting sort. Most production systems use LSD radix sort because it generalises cleanly to arbitrary key widths and parallelises well.

The most significant digit form processes digits from the top down. It is faster in some real-world settings because it can short-circuit: once a bucket contains only one element, that sub-array is sorted and can be skipped entirely. MSD radix sort is the variant you will find in string-sorting routines and in some JavaScript engines for sorting short identifiers. It is also the basis of trie-style data structures, where the recursion stops when buckets have a single element.

Why the complexity looks different

The standard complexity notation for radix sort is O(w · n), where n is the number of elements and w is the number of digits in the longest key. For fixed-width integers, such as 32-bit values, w is constant, so the whole thing collapses to O(n). That is why it is sometimes described as a linear-time sorting algorithm, even though it is not universally faster than quicksort for small inputs.

The constant factors matter a lot. Each pass walks the array, allocates a counting buffer of base size, and writes back into the input. Memory bandwidth often becomes the real bottleneck, especially on modern hardware where L2 cache misses hurt more than arithmetic cost. Practitioners at a small data engineering outfit in Surry Hills learned this the hard way when their first cut kept being beaten by std::sort until they restructured the passes to scan memory sequentially.

Implementing radix sort in practice

A clean reference in C is the easiest way to see what is going on. A minimal implementation walks the array four times for 32-bit integers under base-256, calling a counting-sort subroutine on each byte. Pointer arithmetic matters here, and the inner loops should be tight. For anyone brushing up on low-level details, the C programming tutorials on hello ML walk through the buffer management that makes a fast implementation possible.

The counting subroutine typically uses two passes: one to count occurrences and one to compute prefix sums, which gives the position of each element in the sorted output. Writing back into the input array, rather than allocating a new one each pass, reduces allocator pressure dramatically. Some implementations add a final copy-back step, others toggle between two arrays using a flag variable. Choosing a base that is a power of two also lets you replace division and modulo with simple bit-shifts and masks.

Edge cases and practical pitfalls

Signed integers complicate things because the sign bit would otherwise be processed as just another digit. The standard fix is to flip the sign bit during processing, or to handle negatives by offsetting them into unsigned space first. Forgetting this is a classic bug, and it shows up in code review far more often than you would expect.

Common pitfalls to keep in mind

Performance traps also include catching the moment when an input is already sorted. Comparison sorts can short-circuit on that, radix sort cannot. For mixed workloads, hybrid routines that switch to insertion sort for tiny sub-arrays are common. Profile first, optimise second.

Where radix sort fits in a modern workflow

The algorithm is at its best when keys are fixed-width integers and input sizes are large. Database engines use it for index scans, network monitoring tools use it for packet ordering by timestamp, and compilers use it for instruction scheduling. It is less useful for floating-point keys, strings of variable length, or small arrays where quicksort wins on overhead.

Scenarios where it pays off

For people building data structures and wanting to compare sort-based techniques, looking at related counting structures can pay off. A Fenwick tree walkthrough covers a different counting primitive that complements radix sort nicely for range queries on the resulting sorted array. Pairing the two gives both order and prefix statistics in essentially linear time.

Finally, radix sort shows up in competitive programming more often than newcomers realise. On the problem-solving archives you will find exercises that hinge on noticing when a constraint of, say, n ≤ 10⁶ with values bounded by 10⁹ is solvable with a w·n pass count rather than n log n. Recognising that tipping point is what separates a working submission from one that times out, and it is a habit that transfers directly to real production work across Sydney, Melbourne and Brisbane engineering teams.