What is Counting Sort?
Learn how counting sort uses value tallies and prefix sums to sort integers in linear O(n + k) time without comparisons.
Expected Interview Answer
Counting sort sorts integers by counting how many times each distinct value occurs, converting those counts into prefix sums that give each value its final position, and placing elements directly into the output array in O(n + k) time, where k is the range of input values.
It first builds a count array indexed by value, incrementing a slot for every occurrence in the input, which takes O(n) time. It then transforms that count array into a running total (prefix sum), so each slot tells you how many elements are less than or equal to that value, which fixes the final index range for that value. A final pass walks the input, usually from right to left, placing each element at the position given by its prefix-sum count and then decrementing that count, which makes the sort stable. Because it never compares elements pairwise, counting sort beats the O(n log n) comparison-sort lower bound, but it only works for small, known integer (or integer-mappable) ranges, since its cost and memory scale with k, not just n.
- O(n + k) linear time, beating comparison-sort limits
- Stable when implemented with the right-to-left placement pass
- Simple to implement with just arrays, no comparisons
- Ideal building block for radix sort
AI Mentor Explanation
A scorer tallying a season’s worth of individual innings scores, all between 0 and 50, keeps a tally sheet with one row per possible score instead of comparing innings pairwise. Every dismissal increments the tally row matching that exact score, which takes one pass through the whole season’s data. Running totals across the tally sheet then tell the scorer exactly how many slots in the final ranked list belong to each score band, so a second pass places every innings directly into its slot without ever comparing two innings to each other. This only works cleanly because scores are bounded between 0 and 50 — if scores could be any huge number, the tally sheet would become impractically large.
Step-by-Step Explanation
Step 1
Build the count array
Scan the input once, incrementing count[value] for every element, sized to the known value range k.
Step 2
Convert to prefix sums
Accumulate counts left to right so count[value] now equals how many elements are <= value.
Step 3
Place elements using the counts
Walk the input right to left, put each element at position count[value]-1 in the output, then decrement count[value].
Step 4
Copy back if needed
The output array is fully sorted; copy it over the original if in-place semantics are required by the caller.
What Interviewer Expects
- State the O(n + k) time and O(k) extra space complexity
- Explain why it is not a comparison sort and how that beats the O(n log n) lower bound
- Describe the right-to-left placement pass that makes it stable
- Recognize the limitation: only works well for small, known integer ranges
Common Mistakes
- Applying counting sort to data with a huge or unknown value range, blowing up memory
- Forgetting the prefix-sum step, which is what maps counts to final positions
- Placing elements left to right instead of right to left, which breaks stability
- Calling it a comparison sort when it never compares two elements directly
Best Answer (HR Friendly)
“Counting sort works by tallying how many times each value appears, then using those tallies to figure out exactly where each value belongs in the final sorted array, without ever comparing two elements directly. I would use it when I know the data is integers within a small, bounded range, since it runs in linear time, but it is not a general-purpose sort.”
Code Example
def counting_sort(arr, k):
# arr contains integers in [0, k]
counts = [0] * (k + 1)
for value in arr:
counts[value] += 1
for i in range(1, k + 1):
counts[i] += counts[i - 1]
output = [0] * len(arr)
for value in reversed(arr):
counts[value] -= 1
output[counts[value]] = value
return outputFollow-up Questions
- Why does counting sort not violate the O(n log n) comparison-sort lower bound?
- How would you adapt counting sort for negative numbers?
- How is counting sort used as a subroutine inside radix sort?
- What happens to counting sort’s efficiency if the value range k is much larger than n?
MCQ Practice
1. What is the time complexity of counting sort on n elements with value range k?
Counting sort makes two linear passes over the input plus a pass over the count array of size k, giving O(n + k).
2. What makes counting sort stable when implemented correctly?
Walking the input from right to left and decrementing the count after each placement preserves the relative order of equal elements.
3. Counting sort is best suited for which kind of input?
Its cost and memory scale with the value range k, so it only pays off when k is small and known in advance.
Flash Cards
What is counting sort’s time complexity? — O(n + k), where k is the range of possible values.
How does counting sort determine final positions? — By converting per-value counts into prefix sums that mark the last index each value can occupy.
How do you make counting sort stable? — Place elements by scanning the input right to left and decrementing the prefix-sum count after each placement.
What is the main limitation of counting sort? — It only works efficiently when the input is integers within a small, known range k.