Counting Sort

Introduction

Counting sort is a non-comparison-based sorting algorithm that sorts elements by counting the number of occurrences of each distinct value in the input. Unlike comparison-based algorithms such as quicksort and merge sort, counting sort does not compare elements against each other. Instead, it uses the values themselves as indices into a counting array, achieving O(n + k) time complexity where n is the number of elements and k is the range of input values.

The algorithm was first described by Harold H. Seward in 1954. It operates by determining, for each element, how many elements are less than it. This information is then used to place each element directly into its correct position in the output array. Because it bypasses the comparison-based lower bound of O(n log n), counting sort can be significantly faster than any comparison-based algorithm when the range of values k is not significantly larger than n.

Counting sort is a stable algorithm, meaning elements with equal values appear in the output in the same order as they appear in the input. This stability property makes counting sort particularly valuable as a subroutine in radix sort, which sorts integers digit by digit using a stable sort at each digit position.

"Counting sort assumes that each of the n input elements is an integer in the range 0 to k, for some integer k. When k = O(n), the sort runs in O(n) time." -- Thomas H. Cormen, Introduction to Algorithms

How It Works

Basic Approach

Counting sort works in three main phases:

1. Count occurrences: Create a count array of size k + 1 (where k is the maximum value in the input). Iterate through the input array and, for each element, increment the corresponding position in the count array.
2. Compute cumulative counts: Transform the count array so that each position contains the sum of all counts up to and including that position. After this step, count[i] tells you how many elements are less than or equal to i.
3. Build the output: Iterate through the input array from right to left. For each element with value v, place it at position count[v] - 1 in the output array, then decrement count[v]. The right-to-left traversal ensures stability.

Key Insight

The cumulative count array effectively encodes the final position of each element. If count[v] = p after the cumulative step, it means there are exactly p elements with values less than or equal to v. Therefore, the last occurrence of value v should go at position p - 1 in the output. Each time we place an element with value v, we decrement count[v] so the next element with the same value goes one position earlier.

Algorithm and Pseudocode

procedure countingSort(A : array of non-negative integers, k : int) // k is the maximum value in A n := length(A) // Step 1: Create and populate count array count := new array of size k + 1, initialized to 0 for i := 0 to n - 1 do count[A[i]] := count[A[i]] + 1 end for // Step 2: Compute cumulative counts for i := 1 to k do count[i] := count[i] + count[i - 1] end for // Step 3: Build output array (traverse input right to left for stability) output := new array of size n for i := n - 1 down to 0 do output[count[A[i]] - 1] := A[i] count[A[i]] := count[A[i]] - 1 end for // Copy output back to A for i := 0 to n - 1 do A[i] := output[i] end forend procedure

The algorithm requires knowing the maximum value k in advance, or it can be computed with a preliminary pass through the array. The final loop traverses the input from right to left to ensure stability: among elements with equal values, the one appearing later in the input is placed at a higher index in the output.

Time and Space Complexity

When Is Counting Sort Efficient?

Counting sort is efficient when k = O(n), meaning the range of values is proportional to the number of elements. In this case, the algorithm runs in O(n) time, which is better than the O(n log n) lower bound for comparison-based sorting. However, if k is much larger than n (e.g., sorting 100 elements with values up to 1,000,000), the algorithm wastes both time and space initializing and traversing the large count array.

Comparison lower bound: The O(n log n) lower bound applies only to comparison-based sorting algorithms. Counting sort bypasses this bound because it uses element values as array indices rather than comparing elements to each other. This is why it can achieve linear time.

Worked Example

Sort the array A = [4, 2, 2, 8, 3, 3, 1] using counting sort. The maximum value k = 8.

Step 1: Count Occurrences

Step 2: Cumulative Counts

Reading: count[3] = 5 means there are 5 elements with value 3 or less.

Step 3: Build Output (right to left)

Final sorted array: [1, 2, 2, 3, 3, 4, 8]

Advantages and Disadvantages

Advantages

• Linear time: Runs in O(n + k) time, which is O(n) when k = O(n). This beats the O(n log n) comparison-based lower bound.
• Stable: Preserves the relative order of elements with equal values, making it suitable as a subroutine in radix sort.
• Simple: Easy to implement and understand.
• Deterministic: No randomness involved; performance is completely predictable.
• No comparisons: Does not compare elements against each other, avoiding the comparison-based lower bound.

Disadvantages

• Limited to integers: Can only sort non-negative integers or values that can be mapped to non-negative integers.
• Space-inefficient for large ranges: Requires O(k) space for the count array. If k is very large relative to n, this wastes memory.
• Not in-place: Requires an auxiliary output array of size n in addition to the count array.
• Not suitable for floating-point numbers: Cannot directly handle real numbers or complex objects without a mapping to integers.
• Impractical for large k: Sorting 10 integers in the range 0 to 1,000,000 would require a count array of a million entries.

Comparison with Other Algorithms

Counting Sort vs. Radix Sort: Radix sort uses counting sort as a subroutine, applying it to each digit of the numbers. While counting sort sorts by the entire value, radix sort handles larger ranges by decomposing values into digits. For d-digit numbers with base-k digits, radix sort runs in O(d(n + k)) time.

Counting Sort vs. Quick Sort: Quicksort is a comparison-based algorithm with O(n log n) average time. When k = O(n), counting sort's O(n) time makes it significantly faster. However, quicksort works on any comparable data type and requires much less auxiliary space.

Counting Sort vs. Bucket Sort: Both are non-comparison sorts that distribute elements into buckets. Counting sort uses one "bucket" per distinct value, while bucket sort typically uses a fixed number of buckets and sorts within each bucket. Bucket sort handles floating-point numbers but requires uniform distribution for O(n) average time.

Implementation Notes

Handling Negative Numbers

The basic counting sort assumes non-negative integers. To handle negative numbers, find the minimum value in the input, offset all values by subtracting the minimum (making all values non-negative), sort using standard counting sort, and then add the minimum back to each element in the output.

procedure countingSortWithNegatives(A : array) minVal := minimum(A) maxVal := maximum(A) k := maxVal - minVal count := new array of size k + 1, initialized to 0 // Offset values by minVal for i := 0 to length(A) - 1 do count[A[i] - minVal] := count[A[i] - minVal] + 1 end for // ... cumulative counts and output as before, // using A[i] - minVal as the indexend procedure

Simplified Version (In-Place Variant)

When stability is not required (i.e., when not used as a subroutine in radix sort), a simpler version can be used that writes elements back directly from the count array:

procedure simplifiedCountingSort(A : array, k : int) count := new array of size k + 1, initialized to 0 for each element in A do count[element] := count[element] + 1 end for index := 0 for i := 0 to k do while count[i] > 0 do A[index] := i index := index + 1 count[i] := count[i] - 1 end while end forend procedure

This simplified version is not stable and loses any associated data (such as satellite data in key-value pairs), but it is simpler and does not require an output array.

Use as a Subroutine in Radix Sort

Counting sort's stability is critical when used within radix sort. Radix sort processes digits from least significant to most significant (LSD) or vice versa (MSD). At each digit position, counting sort must preserve the order established by previous passes. If the subroutine were not stable, the final result would be incorrect.

Applications

• Radix sort subroutine: The primary use of counting sort in practice is as the stable sorting subroutine within radix sort.
• Sorting small integers: Efficient for sorting arrays of small non-negative integers, such as exam scores (0-100), ASCII characters (0-127), or age values (0-150).
• Histogram generation: The counting phase naturally produces a histogram of value frequencies, useful in image processing and statistical analysis.
• String sorting: Can be used to sort strings by individual characters when combined with radix sort (as in suffix array construction algorithms).
• Database operations: Sorting records by a small integer key (such as category ID or status code) where the key range is known and limited.
• Suffix array construction: Advanced algorithms for building suffix arrays use counting sort as a key building block.

References

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction to Algorithms, 4th Edition. MIT Press, 2022. Chapter 8: Sorting in Linear Time.
• Knuth, D. E. The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd Edition. Addison-Wesley, 1998. Section 5.2: Internal Sorting.
• Seward, H. H. "Information Sorting in the Application of Electronic Digital Computers to Business Operations." Master's thesis, MIT, 1954.
• Sedgewick, R. and Wayne, K. Algorithms, 4th Edition. Addison-Wesley, 2011. Key-Indexed Counting.