Counting Sort runs in linear O(n + k) time, where n is the number of elements and k is the range of input values. It performs well when the range is not much larger than the number of elements, and it applies only to integer keys within a bounded range.

This chapter covers how Counting Sort works, how to implement it, and when it outperforms comparison-based sorting algorithms.

Counting Sort is a non-comparison-based sorting algorithm. It works by counting the number of occurrences of each distinct value in the input, then using those counts to place each element directly into its correct position in the output.

The algorithm runs in three stages. First, build a count array where index i stores how many times value i appears in the input. Second, transform the count array into a cumulative (prefix sum) array, where each index gives the position of the last element with that value. Third, iterate through the input from right to left, placing each element at the position indicated by the cumulative count and decrementing that count.

The algorithm has three key properties:

Counting replaces comparing. Instead of determining relative order by comparing pairs of elements, the algorithm determines absolute positions by knowing exactly how many elements are smaller than each value.

Breaking the O(n log n) Barrier

Every comparison-based sorting algorithm (Merge Sort, Quick Sort, Heap Sort) must make at least O(n log n) comparisons. This is provable using a decision tree argument: with n! possible permutations of n elements, at least log2(n!) comparisons are needed to distinguish between them, and log2(n!) is O(n log n).

Counting Sort sidesteps this lower bound because it never compares elements. It uses the values themselves as indices into an array, extracting ordering information from the values rather than from pairwise comparisons. This is why the time complexity depends on both n (number of elements) and k (range of values) rather than just n.

The algorithm has five steps. Each is explained below, followed by a flowchart that ties them together.

Step 1: Find the Range

Scan the input array to find the minimum and maximum values. The range k = max - min + 1 determines the size of the count array. When the elements are all non-negative with a known maximum, the scan can be skipped and the known range used directly.

Step 2: Count Occurrences

Create a count array of size k, initialized to all zeros. Iterate through the input and increment count[value - min] for each element. After this step, count[i] gives the number of times the value (i + min) appears in the input.

Step 3: Compute Cumulative Counts (Prefix Sum)

Transform the count array by computing a running sum from left to right. Replace each count[i] with the sum of all counts from index 0 through i. After this step, count[i] gives the number of elements with a value less than or equal to (i + min). This means count[i] is the position (one-indexed) where the last element with value (i + min) should be placed in the output.

Step 4: Build the Output Array (Right to Left)

Create an output array of the same size as the input. Iterate through the input array from right to left. For each element, look up its cumulative count, place the element at position count[value - min] - 1 in the output, and decrement the count. The right-to-left traversal is what makes the sort stable, preserving the relative order of equal elements.

Step 5: Copy Back

Copy the output array back into the original array (or return the output array directly).

The right-to-left traversal in Step 4 is what produces stability. If two elements have the same value, the one that appears later in the input should end up at a higher index in the output. Going right to left and decrementing the count each time places the rightmost duplicate first (at the highest valid position), then the next one at the position just before it, and so on. This preserves the original relative order of equal elements.

Here, n is the number of elements in the input and k is the range of values (max - min + 1).

The time complexity breaks down as follows:

When k is O(n) or smaller (for example, sorting exam scores from 0 to 100 for 10,000 students), the algorithm runs in O(n) time. When k is much larger than n (say, sorting 10 integers that range from 0 to 10 million), the O(k) term dominates and Counting Sort becomes impractical.

Stability

Counting sort is stable, and stability is what makes it usable as the inner pass of radix sort. The right-to-left traversal in Step 4 is the mechanism: the rightmost duplicate is placed at the highest valid position, and each earlier duplicate goes just before it. Equal elements end up in the output in the same order they appeared in the input.

A left-to-right traversal would still sort correctly but would reverse the relative order of equal elements, which would break radix sort when counting sort is used as its subroutine.

Comparison with Other Sorting Algorithms

Counting Sort runs faster than comparison sorts when k is small, but it trades that speed for extra memory and a strict constraint on input type.

Good Use Cases

When Not to Use

The Decision Rule

A practical rule of thumb: use Counting Sort when k (the range of values) is at most O(n). If k is significantly larger than n, comparison-based sorts like Merge Sort or Quick Sort will outperform it in both time and space.