Counting Sort

Counting Sort: O(n + k) Sorting

Mathematical Definition

Let A be an input array of length n, where each element A[i] is an integer such that 0 ≤ A[i] ≤ k. The algorithm uses an auxiliary array C of size k + 1, and an output array B of size n.

The time complexity is directly derived from the loops. The first and third loops iterate k times, while the second and fourth loops iterate n times. Thus, the total time complexity is O(n + k). The space complexity is O(n + k) required for the arrays B and C.

Key Concepts

• Non-Comparison Sorting: Elements are never directly compared to each other. Instead, the algorithm uses the element values themselves as array indices to count their frequency.
• Stability: Counting Sort is inherently stable if the elements are placed into the output array by iterating backwards from n-1 to 0. Stability means that multiple elements with the same key value will retain their relative order in the sorted output, which is crucial when Counting Sort is used as a subroutine in Radix Sort.
• Prefix Sum (Accumulation): After computing the raw frequency of each element in the C array, the algorithm computes a prefix sum: C[i] = C[i] + C[i-1]. After this step, C[i] explicitly represents the number of elements less than or equal to i, which directly correlates to the 1-based index where the element should be placed in the final array.
• Dependency on k: The efficiency of Counting Sort heavily depends on k (the maximum value in the array). If k is O(n), the algorithm runs in linear time. However, if k is significantly larger than n (e.g. k = O(n²) or k = O(2ⁿ)), the algorithm performs poorly compared to O(n log n) comparison sorts and wastes vast amounts of memory.

Historical Context

Counting Sort was invented by Harold H. Seward in 1954. Seward developed it as part of his master's thesis at MIT, titled "Information sorting in the application of electronic digital computers".

Before Seward's algorithm, Radix Sort was widely known, particularly due to its implementation in mechanical punch-card sorting machines (invented by Herman Hollerith in the late 19th century). However, early computer implementations of Radix Sort struggled with memory management, often requiring linked lists or complex data structures for the 'buckets'. Seward recognized that by using an auxiliary array to simply count the items first, Radix Sort could be implemented efficiently using contiguous arrays. Counting Sort fundamentally serves as the stable, linear-time sorting subroutine that makes modern, in-memory Radix Sort practical.

Real-world Applications

• Subroutine in Radix Sort: Counting Sort is most commonly used as the stable sorting algorithm for sorting the individual digits (or bytes) in Radix Sort, allowing integers or strings to be sorted in linear time.
• String Anagrams & Alphabetical Ordering: Sorting strings of characters based on ASCII values (where k=255) or English alphabet (where k=26) is extremely fast with Counting Sort.
• Histogram Generation in Image Processing: Computing the histogram of an 8-bit grayscale image is fundamentally identical to the counting phase of Counting Sort.
• Suffix Array Construction: Efficient algorithms for constructing suffix arrays (like the DC3 algorithm or prefix-doubling) often use Counting Sort/Radix Sort to sort substrings in linear time.

Related Concepts

• Radix Sort — a linear-time sort that heavily relies on Counting Sort as its underlying stable sorting mechanism.
• Sorting — comparison-based sorting algorithms like Quick Sort and Merge Sort which are bounded by Ω(n log n).
• Bucket Sort — another non-comparison sort that distributes elements into buckets before sorting them individually.