Non-Comparison Sorts — Counting, Radix, Bucket

Comparison sorts are bounded below by O(n log n), but when keys are integers or strings in a bounded range you can beat that with counting, radix, and bucket sort — achieving linear time by not comparing elements. Knowing when this is legal (and its space cost) is the interview point.

The core idea

• Counting sort: count occurrences of each key in range [0, k], then place them in order — O(n + k) time and space; stable; only for small integer ranges.
• Radix sort: apply a stable counting sort digit by digit (least-significant first) — O(d·(n + k)) for d digits; great for fixed-width integers/strings.
• Bucket sort: distribute elements into buckets, sort each, concatenate — O(n) average for uniformly distributed data, O(n²) worst.
  These sidestep the O(n log n) comparison lower bound because they exploit key structure, not comparisons.

Sort	Time	Space	Stable	Requires
Counting	O(n + k)	O(n + k)	Yes	small integer range
Radix (LSD)	O(d(n + k))	O(n + k)	Yes	fixed-width keys
Bucket	O(n) avg / O(n²)	O(n)	depends	uniform distribution

Exam Tricks & Tips

• 🎯 Keys are integers/strings in a bounded range → counting/radix can hit O(n), beating O(n log n).
• 🎯 Counting sort's O(k) space makes it impractical when the value range k is huge.
• 🎯 Radix sort processes digits least-significant-first using a stable counting sort per digit.
• 🎯 Bucket sort is O(n) only when data is uniformly distributed across buckets.
• 🎯 These are the exception to "comparison sorting is Ω(n log n)" — because they don't compare.
• ❌ Common mistake: using counting sort when k ≫ n, wasting O(k) time and memory.

Expected pattern

"Sort integers in [0, k]", "sort by digits/characters", maximum gap (bucket sort), or "can you beat O(n log n)?". Interviewers check the range/structure precondition and the space trade-off.

Quick recap

Counting (O(n+k)), radix (O(d(n+k))), and bucket (O(n) avg) sorts beat the O(n log n) comparison bound by exploiting bounded integer/string keys instead of comparing. Counting/radix are stable; watch counting sort's O(k) space when the range is large.

Cover the answer, recall, then check. 11 cards on non-comparison sorts.

Q1. Lower bound for comparison-based sorting?
A1. Ω(n log n).

Q2. How do counting/radix/bucket sorts beat it?
A2. They exploit bounded integer/string key structure instead of comparing elements.

Q3. Counting sort time and space?
A3. O(n + k) time and space, where k is the key range.

Q4. When is counting sort a poor choice?
A4. When the value range k is much larger than n — O(k) time and memory dominate.

Q5. Radix sort complexity?
A5. O(d·(n + k)) for d digits/positions.

Q6. Which sort does radix use per digit, and why must it be stable?
A6. Counting sort; stability preserves the ordering from less-significant digits.

Q7. Bucket sort's average and worst case?
A7. O(n) average (uniform distribution), O(n²) worst (all in one bucket).

Q8. Are counting and radix sorts stable?
A8. Yes.

Q9. Radix sort digit order (LSD)?
A9. Least-significant digit first, moving toward the most significant.

Q10. Maximum Gap problem — which sort helps?
A10. Bucket sort (pigeonhole), achieving O(n) by bounding the gap within/between buckets.

Q11. Precondition to legally use counting sort?
A11. Keys are non-negative integers (or mappable) within a small, known range.

Comparison sorts can't beat O(n log n), but when keys are integers or strings in a bounded range, counting, radix and bucket sort break that barrier and reach O(n). Knowing when this is legal — and when it isn't — is a sharp interview differentiator.

Core idea: instead of comparing elements, use the keys themselves as array indices (or digit buckets). This sidesteps the comparison lower bound entirely, achieving linear time when the key range is small relative to n.

How it works

Beginner — counting sort

For integers in [0, k]: count each value's occurrences, then rebuild the array from the counts.

count[v] += 1 for each v          # tally
# prefix-sum counts, then place each element at its position

O(n + k) time, O(k) space. Linear when k = O(n); it is also stable if you place elements right-to-left using prefix sums.

Intermediate — radix sort

Sort integers (or fixed-length strings) digit by digit, least-significant first, using a stable counting sort per digit.

• d digits, each pass O(n + base) → O(d·(n + base)), effectively O(n) when d and base are small/constant.
• Stability per digit is essential — without it earlier digit order is destroyed.

Advanced — bucket sort and the legality condition

Bucket sort distributes n elements (assumed roughly uniformly distributed) into n buckets, sorts each bucket (insertion sort), and concatenates → O(n) average, O(n²) worst if all land in one bucket. The universal caveat: these sorts are linear only when the key range/digit count is bounded. For arbitrary 64-bit keys or general comparables, radix's d factor or counting's k blows up and comparison sorts win. They also need extra space and only apply to integer-like keys, not arbitrary objects.

Worked example

Counting sort [4, 2, 2, 8, 3, 3, 1], k=8. Counts: 1:1, 2:2, 3:2, 4:1, 8:1. Emit in value order: [1, 2, 2, 3, 3, 4, 8]. Total work O(n + k) = O(7 + 9) — linear, no comparisons made. If k were, say, 10⁹ this would waste huge memory and lose to O(n log n).

When to use it

• Counting sort: small integer range (grades, ages, ASCII), and as radix's inner sort.
• Radix sort: fixed-width integers or strings (phone numbers, IDs, dates).
• Bucket sort: uniformly distributed floats in [0,1), or data known to spread evenly.
  Signal: "integers in range 0..k", "sort n numbers where each ≤ K", bounded keys.

Tricks & gotchas

• Linear time requires a bounded key range/digit count — state this precondition explicitly.
• Counting and radix need O(n + k) extra space — not in-place.
• Radix's per-digit sort must be stable, or the result is wrong.
• Mnemonic: "Use the key as an index — linear, but only for bounded ranges."

Key formulas

• Counting sort: O(n + k) time and space (k = key range); stable; good when k = O(n).
• Radix sort: O(d(n + b)), d digits, base b; uses stable counting sort per digit.
• Bucket sort: O(n) average for uniform input; O(n²) worst.
• These beat Ω(n log n) by not comparing pairs.
• Radix on w-bit ints, base 2^r: d = ⌈w/r⌉ passes.

Usage: use counting/radix only when the key range is O(n) or the width is small.

Worked Example

Problem: Sort [4, 2, 2, 8, 3, 3, 1] using counting sort (values are small integers).

Solution: Counting sort tallies how many times each value occurs, then writes values back in order — it never compares two elements.

Count occurrences (values range 1..8):

value	1	2	3	4	8
count	1	2	2	1	1

Emit each value count times, in increasing value order:
1 (×1), 2 (×2), 3 (×2), 4 (×1), 8 (×1) → [1, 2, 2, 3, 3, 4, 8].

With n items and value range k, this is O(n + k) time and O(k) space — beating the O(n log n) comparison-sort lower bound because it exploits the bounded range.

(Radix sort applies counting sort digit by digit for larger numbers; bucket sort distributes into ranges.)

Answer: [1, 2, 2, 3, 3, 4, 8].