Counting Sort vs Radix Sort

Counting Sort tallies every distinct value, needing O(k) memory for value range k. Radix Sort sidesteps the memory blow-up by sorting digit by digit, applying a stable Counting Sort on each digit so k stays tiny (just 10 for decimal digits).

Use Counting Sort when the value range k is small (scores 0-100, ages). Use Radix Sort when values are large integers but have a fixed number of digits — it keeps memory low while still beating O(n log n). Both are stable and non-comparison.

The decision comes down to one number: the range of your keys relative to how many items you have.

Counting Sort wins when the range is small and known. Sorting a million exam scores from 0 to 100, ages from 0 to 120, or bytes from 0 to 255 — here k is tiny, so O(n + k) is effectively O(n) and you cannot do better. It is a single counting pass and a single output pass.

Counting Sort collapses when the range is large. Sorting a thousand 32-bit integers would require a counting array of over four billion entries to hold values you mostly do not have. The memory cost is O(k) regardless of how few items you are actually sorting, which makes it unusable for sparse data over a wide range.

Radix Sort is the fix for exactly that case. It applies a stable Counting Sort one digit at a time, so the counting array only ever needs as many slots as there are possible digit values — ten for decimal, or 256 if you process a byte at a time. Sorting those same 32-bit integers becomes four passes with a 256-entry array instead of one pass with a four-billion-entry array.

This dependency is worth stating explicitly, because it is often missed: Radix Sort requires a stable sub-sort to work at all. Each pass must preserve the ordering established by the previous, less significant digit. If the per-digit sort were unstable, sorting by the tens digit would scramble the units ordering and the algorithm would simply produce wrong output. Counting Sort's stability is not an incidental nice-to-have here — it is the load-bearing property.

A quick rule: if k is comparable to n or smaller, use Counting Sort. If k is enormous but keys have a bounded number of digits, use Radix Sort. If keys are unbounded, arbitrary-precision or need a custom comparison, neither applies and you are back to comparison sorting.