Learn the vocabulary of tallying value occurrences and placing elements directly into sorted position.
0 / 5 completed
1 / 5
At standup, a dev mentions counting how many times each distinct value occurs across a collection of integers within a known, small range, then using those counts to place every element directly into its final sorted position. What is this algorithm called?
Counting sort is exactly this: counting sort tallies how many times each distinct value occurs across a collection of integers confined to a known, small range, then uses those counts to compute each value's final position and place every element directly into a sorted output array, without ever comparing two elements to each other. A hash collision is an unrelated hash-table concept about two keys sharing a bucket. This count-then-place approach is exactly why counting sort runs in linear time relative to the input size plus the value range, as long as that range stays small.
2 / 5
During a design review, the team picks counting sort for sorting a huge list of integers confined to a small, known range, specifically because tallying occurrences per value and placing elements directly avoids ever comparing two elements to each other. Which capability does this provide?
Counting sort here provides Linear-time sorting when the value range is small, since the cost scales with the number of elements plus the size of the value range rather than with any per-pair comparisons, which is exactly what lets it beat the O(n log n) comparison floor whenever the range of possible values stays small. A comparison-based sort, however well optimized, can never beat that comparison floor regardless of how small the value range happens to be. This small-range, count-then-place behavior is exactly why counting sort is favored for sorting integers confined to a known, small range, like exam scores or small counters.
3 / 5
In a code review, a dev notices a sorting feature over a huge list of integers known to fall within a small, fixed range uses a general comparison-based sort, instead of tallying occurrences per value and placing elements directly into sorted position. What does this represent?
This is a missed counting-sort opportunity, since tallying occurrences per value and placing each element directly into its final position would sort the list in linear time instead of paying the comparison-based O(n log n) floor. A cache eviction policy is an unrelated concept about discarded cache entries. This ignore-the-small-range pattern is exactly the kind of missed speedup a reviewer flags once the value range is confirmed small and fixed.
4 / 5
An incident report shows a sort of integers known to fall within a small, fixed range ran slower than expected under load, because it used a general comparison-based sort instead of tallying occurrences per value. What practice would prevent this?
Switching to counting sort's tally-and-place approach avoids per-pair comparisons entirely by placing values directly. Continuing to use a general comparison-based sort over a small, fixed integer range regardless of how small and fixed the value range actually is is exactly what caused the issue described in this incident. This tally-and-place approach is the standard fix once the value range is confirmed small and fixed relative to the input size.
5 / 5
During a PR review, a teammate asks why the team reaches for counting sort instead of a comparison-based sort like quicksort, given that quicksort works on any orderable data, not just integers in a small range. What is the reasoning?
Counting sort beats the comparison floor entirely when the value range is small and known in advance, since its cost scales with that range rather than with per-pair comparisons, but that same dependence makes it impractical once the range is huge or unbounded, while a comparison-based sort like quicksort works on any orderable type regardless of the value range. This is exactly why counting sort is reserved for small, known ranges, while a comparison-based sort remains the general-purpose fallback.