Counting Sort
Counting sort is a non-comparison-based sorting algorithm that operates by counting the occurrences of each distinct element and using those counts to dete...
Sorting Without Comparisons
Counting sort is a non-comparison-based sorting algorithm that operates by counting the occurrences of each distinct element and using those counts to determine the final positions of elements. Because it does not compare elements against each other, it can break the O(n log n) lower bound that applies to all comparison-based sorts.
The algorithm works in three steps. First, create a count array of size k where k is the range of input values. Initialize every count to zero. Second, scan the input array and increment the count at the index corresponding to each element's value. Third, convert the count array into a cumulative sum array where each position holds the number of elements less than or equal to that value. Finally, scan the input array again from right to left, placing each element at its correct output position using the cumulative counts and decrementing the count to handle duplicate values.
A worked example: sort the array 4, 2, 2, 8, 3, 3, 1 where values range from 1 to 8. Count array after first scan: index 1 has 1, index 2 has 2, index 3 has 2, index 4 has 1, index 8 has 1, others zero. Cumulative sum: index 1 is 1, index 2 is 3, index 3 is 5, index 4 is 6, index 5-7 are 6, index 8 is 7. Scanning input right to left places elements into output array using cumulative counts, producing 1, 2, 2, 3, 3, 4, 8.
Time complexity is O(n plus k) where n is the number of elements and k is the range of values. Space complexity is O(n plus k) for the count array and output array. When k is O(n), this reduces to O(n) time and space, which is faster than any comparison sort.
Counting sort is stable when the final placement step scans the input from right to left. This stability is essential when counting sort is used as a subroutine in radix sort.
Interview tip: always state the k limitation when discussing counting sort. If the range of values is much larger than n, say k equals n squared, counting sort becomes O(n squared) in time and space, making it worse than merge sort. The algorithm is only beneficial when k is comparable to n.
Implementing Counting Sort Correctly
Implementing counting sort without bugs requires care at several steps. The most common mistakes are handling the offset for non-zero minimum values, building the cumulative sum incorrectly, and scanning in the wrong direction during placement.
When the input values do not start at zero, subtract the minimum value from each element before counting. For example, if values range from 50 to 100, define k as 51 (the range size) and subtract 50 from each element when indexing into the count array. This reduces the space needed from 101 to 51 entries.
Pseudocode: find min and max of the input array. Set k to max minus min plus 1. Allocate count array of size k initialized to zero. For each element x in the input, increment count at index x minus min. Build the cumulative sum: for i from 1 to k-1, count at i equals count at i plus count at i minus 1. Allocate output array of size n. Scan input from right to left: for each element x, compute position as count at x minus min minus 1, decrement count at x minus min, place x at output position.
The right-to-left scan preserves stability. If you scan left to right, equal elements are placed in reverse order, breaking stability.
A worked example of the offset: array is 97, 95, 99, 95, 98. Min is 95, max is 99, k is 5. Adjusted values are 2, 0, 4, 0, 3. Count array: index 0 has 2, index 2 has 1, index 3 has 1, index 4 has 1. Cumulative: 2, 2, 3, 4, 5. Scanning right to left places 98 at position 3, 95 at position 1, 99 at position 4, 95 at position 0, 97 at position 2. Output: 95, 95, 97, 98, 99. Correct.
Interview tip: implement counting sort on paper during an interview and explicitly mention the right-to-left scan for stability. Most candidates know that counting sort exists but cannot implement it correctly, so a clean implementation is a strong differentiator.
When Counting Sort Excels
Counting sort is the optimal choice for sorting when the value range is small relative to the number of elements. Understanding the exact conditions makes it easier to recognize when to apply it and when to use a comparison sort instead.
The fundamental condition is k being O(n). In practice this means the number of distinct possible values is at most a small constant multiple of the number of elements you are sorting. Common examples include sorting ages (range 0 to 150), sorting grades (range 0 to 100), sorting days of the week (range 0 to 6), sorting characters in a string (range 0 to 255 for ASCII), and sorting small integer identifiers.
Counting sort is also essential as a subroutine within radix sort. Radix sort processes one digit at a time, and each digit has a range of 0 to 9 for decimal or 0 to 255 for byte-level processing. Counting sort on each digit in turn, from least significant to most significant, sorts the entire array in O(n times d) time where d is the number of digits.
A real-world application: a school needs to sort 10,000 student exam scores where each score is an integer from 0 to 100. Merge sort takes O(n log n) which is approximately 130,000 operations. Counting sort takes O(n plus k) which is O(10,100) operations. For this use case, counting sort is over 10 times faster both theoretically and in practice.
Another application is frequency analysis in text processing. Counting sort on characters in a document runs in O(n) where n is the document length and k is 256 for the ASCII character set. This is the most efficient possible approach.
Time complexity: O(n plus k). Space complexity: O(n plus k). Stable: yes when implemented correctly with right-to-left scan.
Interview tip: when given a problem involving sorting integers with a known bounded range, immediately identify counting sort as the target algorithm and compute the expected O(n plus k) complexity explicitly. This shows you recognize the optimal tool for the constraints.