Counting Sort: Space-Time Tradeoffs
You'll learn when counting sort is practical by comparing the range of input values to the number of elements.
The Core Tradeoff
Counting sort achieves O(n + k) time complexity, where n is the number of elements and k is the range of input values (from minimum to maximum). This breaks the O(n log n) comparison-sort barrier, but there's a catch: it also requires O(k) extra space for the counting array.
The big question: when does this tradeoff make sense?
When Counting Sort Shines
Counting sort is practical when k is small relative to n—ideally when k = O(n).
Example: Sorting 1,000,000 exam scores (ranging 0-100):
- n = 1,000,000
- k = 101
- Time: O(1,000,000 + 101) ≈ O(n) — blazingly fast!
- Space: O(101) — negligible
When Counting Sort Fails
If k >> n (k much larger than n), the algorithm becomes impractical.
Example: Sorting 100 arbitrary 32-bit integers:
- n = 100
- k = 4,294,967,296 (range of 32-bit values)
- Time: O(100 + 4 billion) ≈ O(k) — terrible!
- Space: O(4 billion integers) — millions of bytes wasted
Analogy: It's like reserving a hotel room for every possible guest ID number (0 to 4 billion) when you only expect 100 guests. The infrastructure cost overwhelms the benefit.
Practical Rule of Thumb
Use counting sort when:
- You know k in advance
- k ≤ 10n (rough guideline)
- Space for k integers is available
Otherwise, stick with O(n log n) comparison sorts like quicksort or mergesort.
Key Takeaway: Counting sort trades space for speed—it's incredibly fast when the value range k is small compared to the dataset size n, but becomes impractical when k dominates.