aloalgo.comRadix and Counting Sort
These are non-comparison sorts that achieve O(n) time by exploiting properties of the input (integer values, fixed range). They bypass the O(n log n) lower bound of comparison-based sorting.Counting Sort
Idea: Count occurrences of each value, then use the counts to place elements in sorted order. Works when values are integers in a known range [0, k].- Time: O(n + k) where k is the range of values
- Space: O(n + k)
- Stable: Yes (with proper implementation)
- Limitation: Only works for integers with limited range
Stable Counting Sort
For stability (preserving relative order of equal elements), use prefix sums to determine positions:Radix Sort
Idea: Sort integers digit by digit, from least significant to most significant (LSD) or vice versa (MSD). Uses a stable sort (usually counting sort) for each digit.- Time: O(d * n) where d is the number of digits
- Space: O(n + k) where k is the radix (base, usually 10)
- Stable: Yes
- Best for: Fixed-length integers, strings of same length
Comparison
| Algorithm | Time | Space | Stable | Use Case |
|---|---|---|---|---|
| Counting Sort | O(n + k) | O(n + k) | Yes | Small range integers |
| Radix Sort | O(d * n) | O(n + k) | Yes | Fixed-length integers/strings |
When to Use
| Situation | Best Choice | Why |
|---|---|---|
| Integers in range [0, k] | Counting Sort | O(n + k), simple |
| Large integers, small digits | Radix Sort | O(d * n), handles big numbers |
| Fixed-length strings | Radix Sort | Sort character by character |
| Range k > n log n | Comparison Sort | O(n log n) beats O(n + k) |
Interview Tips
- Know the constraints: These only work for specific inputs (integers, limited range). Always clarify input constraints.
- Counting sort as a building block: It's used inside radix sort and bucket sort.
- When k is small: If told values are in range [0, 100], counting sort gives O(n).
- Stability matters for radix: Radix sort requires a stable sub-sort to work correctly.
- Compare to O(n log n): Only faster when k or d is smaller than log n.
Was this helpful?
Company
Practice
Learn
© 2026 aloalgo.com. All rights reserved.