Foundation · Module 4 · Lesson 7
Counting, Radix & Bucket Sort
Exploit key structure to avoid comparisons.
15–25 min readLesson 25 of 123
Lesson 25 of 123
1d streakTheory lesson · Step-by-step
Understand Counting, Radix & Bucket Sort
Exploit key structure to avoid comparisons.
Worked approach
Trace the reasoning step by step
- 1Inspect key constraints and choose counting, radix, or buckets.
- 2Build counts or distribute values by the current key component.
- 3Reconstruct in key order; keep passes stable for radix sort.
- 4Include range size and bucket behavior in the complexity analysis.
Concrete example
Counting-sort [2, 1, 2, 0].
- 1Counts are [1,1,2].
- 2Emit 0 once, 1 once, and 2 twice.
Result [0,1,2,2] is produced in O(n + range).
What must remain true (Loop Invariant)
Non-comparison sorting is valid only when keys expose bounded digits, ranges, or a useful distribution.
Cost Model
Complexity & Trade-offs
OperationTimeSpaceWhy
Counting sort
O(n + k)
O(k)
k is the key range.Radix sort
O(d(n + k))
O(n + k)
d digit passes using a stable inner sort.When to use it
- Creating order before searching, grouping, deduplicating, or scanning.
- Selecting records using stability, memory, and input-shape constraints.
- Turning pairwise decisions into monotonic scans.
Common mistakes
- Comparing time alone while ignoring stability and auxiliary memory.
- Breaking duplicate order when stability is required.
- Quoting average performance without worst-case behavior.
Practice prompts
- Reproduce the worked Counting, Radix & Bucket Sort example without looking at the trace.
- Change one input condition and explain whether the Counting, Radix & Bucket Sort invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check
Can you derive it instead of memorizing it?
State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.