Skip to main content

Radix Sort and Linear in Key Width

What This Concept Is​

Least-significant-digit radix sorting applies stable digit sorts from low to high significance. For k-bit unsigned keys and w-bit digits, choose d = ceil(k/w) passes and radix b = 2^w, with 1 <= w <= k. Counting-sort passes take Theta(d(n+b)) work and O(n+b) auxiliary slots. The final partial digit can use fewer buckets.

For fixed 32-bit keys, four 8-bit passes give Theta(4(n+256)) = Theta(n) as n grows. At least one pass is necessary. This cannot become sublinear in n by dropping the ceiling or treating a digit wider than the key as a fractional pass.

Why It Matters Here​

The phrase "linear time" hides key width and representation. Integer magnitude, string length, digit extraction, and count-array size are part of the contract. Reasoning in these parameters prevents misleading comparisons with a model in which every arbitrary-length comparison is assumed to cost one operation.

Concrete Examples​

Sort [21,12,11,22] in base ten. The stable ones pass gives [21,11,12,22]; the stable tens pass gives [11,12,21,22]. After pass j, records are sorted by their j lowest digits. On the next pass, the new digit establishes major groups while stability preserves the lower-digit order within each group. Reversing ties in the tens pass can place 12 before 11, breaking numeric order.

For 64-bit keys, eight 8-bit passes use 256 counters; four 16-bit passes use 65,536 counters. Fewer passes do not by themselves imply lower elapsed time: initialization and memory behavior differ. Compare full costs and measure.

Common Confusion / Misconceptions​

Stable digit sorting is necessary for this LSD proof, not for every MSD radix algorithm. MSD partitions by the leading digit and recurses within groups; variable-length strings require a defined end-of-string ordering. Bytes are not automatically locale-aware text order.

For fixed-width two's-complement integers, flipping the sign bit maps signed order to unsigned order. Floating-point ordering is not an exponent-XOR trick. For finite IEEE values an order-preserving encoding needs different treatment of negative and nonnegative bit patterns, and zero/NaN policy must be specified. Floating-point sorting is outside this lab's integer contract.

How To Use It​

Choose a representation with a documented total ordering, then prove the digit invariant. Treat arbitrary-precision integers separately: d can grow and digit extraction may have nonconstant cost in the implementation language. Report counts of passes and memory traffic separately from runtime; there is no universal CPU/GPU speed ratio or input-size crossover.

Check Yourself​

  1. Why does the second digit pass need stability?
  2. What is wrong with deriving Theta(n/log n) for fixed-width record sorting?
  3. Which costs grow when the radix increases?
  4. Why must strings and floats have an explicit encoding policy?

Mini Drill or Application​

Build a nonnegative 16-bit LSD sort using your stable counting pass. Test base 16 versus base 256 against a trusted sort. Verify equal-key payload order, zero, the maximum key, and a final partial digit in a 10-bit variant. Derive counts before timing anything. Implementations and analysis are an extension after Lab A; see P4 and P15.

Read This Only If Stuck​

Use CLRS, Skiena, or Sedgewick and Wayne for LSD/MSD radix sorting, digit stability, and representation costs. These links open book indexes; find the named topic in your edition. Use the reading guide for the bounded assignment and worked examples before adding another source.