Loading learning content...
Throughout our exploration of sorting algorithms—from the simple bubble sort to the sophisticated quick sort—we've operated under an implicit assumption: comparison is the only way to determine ordering. We compare elements pairwise, asking 'Is A less than B?', and from these binary decisions, we construct sorted output.
This assumption leads to a mathematical certainty: no comparison-based sorting algorithm can do better than Ω(n log n) in the worst case. This is proven through decision tree analysis—with n! possible permutations and binary comparisons, log₂(n!) ≈ n log n comparisons are necessary.
But what if we challenged this assumption? What if, under certain conditions, we could sort without comparing elements at all?
Counting sort represents a fundamental paradigm shift: instead of asking 'Is A less than B?', we ask 'What value is A?' When values come from a bounded, discrete domain, this question reveals everything we need to know about ordering—without a single comparison.
This page explores the crucial precondition that enables this revolutionary approach: the limited range constraint. Understanding when and why this constraint holds is the key to unlocking linear-time sorting.
Consider a deceptively simple observation: if you know that every element in your array is an integer between 0 and 100, you've gained something profound—you know exactly where each element 'belongs' in the sorted output without comparing it to anything else.
The number 42, by virtue of being 42, belongs after 41 elements that are smaller (0 through 41) and before 58 elements that are larger (43 through 100). No comparison required.
This is direct addressing: the value itself determines position. It's the same principle that makes array indexing O(1)—if you want element 42, you don't search for it, you compute where it is.
Comparison-based sorts like merge sort and quick sort work on any totally ordered set: integers, strings, floating-point numbers, custom objects. They ask only 'Is A ≤ B?' Counting sort sacrifices this generality for speed—it requires integer-like values from a bounded domain.
Let's define the limited range constraint precisely. Given an input array A of n elements:
Definition (Limited Range Property): The input satisfies the limited range property if there exist integers min and max such that for all elements A[i]:
min ≤ A[i] ≤ max
We define the range parameter k = max - min + 1, representing the count of distinct possible values.
Critical Insight: The relationship between n (array size) and k (value range) determines whether counting sort is efficient:
k = O(n): Counting sort achieves O(n) time—faster than any comparison-based sort.k = O(n log n): Counting sort ties with comparison sorts.k = Ω(n²): Counting sort is slower than comparison sorts.k is exponential: Counting sort becomes impractical.| Range k | Counting Sort Time | Comparison Sort Time | Winner |
|---|---|---|---|
| k = 100, n = 10,000 | O(10,100) ≈ O(n) | O(n log n) ≈ 130,000 ops | Counting Sort |
| k = n | O(2n) = O(n) | O(n log n) | Counting Sort |
| k = n log n | O(n log n) | O(n log n) | Tie |
| k = n² | O(n²) | O(n log n) | Comparison Sort |
| k = 2ⁿ (exponential) | Infeasible | O(n log n) | Comparison Sort |
Never evaluate counting sort's efficiency without considering k. Saying 'counting sort is O(n)' is incomplete—it's O(n + k). When k >> n, the algorithm degrades catastrophically. The constraint k = O(n) is typically required for counting sort to be advantageous.
The comparison-based lower bound of Ω(n log n) arises from information theory. With n elements, there are n! possible orderings. Each comparison yields 1 bit of information (yes/no), and distinguishing between n! possibilities requires at least log₂(n!) bits, which is Ω(n log n).
The limited range constraint provides a different source of information: the values themselves. When we know a value is, say, 42, we've gained log₂(k) bits of information in O(1) time—without any comparison.
1234567891011121314151617181920212223
Comparison-Based Sorting:─────────────────────────• Information available: Binary comparisons only• Bits per comparison: 1• Bits needed to distinguish n! orderings: log₂(n!) ≈ n log n• Lower bound: Ω(n log n) comparisons Counting Sort with Range k:───────────────────────────• Information available: Each value ∈ [0, k-1]• Bits per value read: log₂(k)• Total bits available: n × log₂(k) When k = O(n): n × log₂(n) bits available from values alone ≈ n log n bits (enough to determine ordering) Acquired in O(n) time (reading each value once) Key Insight:────────────The values themselves encode the ordering information.We trade the generality of comparisons for thedirectness of value-based positioning.The direct addressing principle:
Imagine sorting mail into mailboxes numbered 1 through 100. You don't compare letters to each other—you look at the address (the value) and put the letter directly in the corresponding mailbox. This is O(n): one operation per letter, regardless of how many letters exist.
Counting sort applies this same principle. Values become indices, and indices become positions. The 'sorting' is implicit in the structure we build.
The limited range property isn't an artificial constraint—it naturally appears in many practical domains. Recognizing these scenarios is crucial for applying counting sort effectively.
When analyzing a sorting problem, ask: 'What is the range of values?' If the answer is a small constant (like ages or scores) or bounded by O(n), counting sort may outperform comparison sorts dramatically. This single question can transform an O(n log n) operation into O(n).
Sometimes data doesn't naturally satisfy the limited range property, but can be transformed to do so. This technique, called coordinate compression or discretization, enables counting sort on data that appears unbounded at first glance.
123456789101112131415161718192021222324252627282930313233343536373839
/** * Transform arbitrary integers to a limited range [0, n-1] * by mapping each unique value to its rank among all values. * * Original: [1000000, 5, 999999, 5, 1000000] * Compressed: [2, 0, 1, 0, 2] * * After compression, k = number of distinct values ≤ n */function coordinateCompress(arr: number[]): { compressed: number[]; decompression: number[];} { // Step 1: Find unique values and sort them const uniqueSorted = [...new Set(arr)].sort((a, b) => a - b); // Step 2: Create value → rank mapping const valueToRank = new Map<number, number>(); uniqueSorted.forEach((val, idx) => valueToRank.set(val, idx)); // Step 3: Compress original array const compressed = arr.map(val => valueToRank.get(val)!); return { compressed, // Use this for counting sort decompression: uniqueSorted // Map rank → original value };} // Example: Sorting with coordinate compressionfunction sortWithCompression(arr: number[]): number[] { const { compressed, decompression } = coordinateCompress(arr); // Now counting sort works: k = decompression.length ≤ n const countingSorted = countingSort(compressed, decompression.length); // Decompress to get original values return countingSorted.map(rank => decompression[rank]);}Coordinate compression requires O(n log n) time (to sort unique values), which seems to defeat the purpose. However, it's useful when: (1) you need to sort the same data multiple times with different criteria, (2) counting sort is part of a larger algorithm like radix sort, or (3) the actual values don't matter, only relative order.
The canonical counting sort assumes values in [0, k-1]. Real data often includes negative numbers or arbitrary ranges like [-50, 50] or [1000, 2000]. This requires a simple but critical adjustment: offset normalization.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354
/** * Normalize an array with arbitrary range [min, max] to [0, k-1] * where k = max - min + 1. * * Example: * Input range: [-5, 5] → Normalized range: [0, 10] * Value -5 → 0, Value 0 → 5, Value 5 → 10 */function normalizeRange(arr: number[]): { normalized: number[]; offset: number; rangeSize: number;} { const min = Math.min(...arr); const max = Math.max(...arr); const rangeSize = max - min + 1; // Subtract min to shift all values to [0, k-1] const normalized = arr.map(val => val - min); return { normalized, offset: min, // Store to denormalize later rangeSize };} // Complete counting sort with offset handlingfunction countingSortWithOffset(arr: number[]): number[] { if (arr.length === 0) return []; const { normalized, offset, rangeSize } = normalizeRange(arr); // Standard counting sort on normalized values const count = new Array(rangeSize).fill(0); for (const val of normalized) { count[val]++; } // Build output const output: number[] = []; for (let val = 0; val < rangeSize; val++) { // Add 'offset' back to denormalize for (let i = 0; i < count[val]; i++) { output.push(val + offset); } } return output;} // Test with negative numbersconsole.log(countingSortWithOffset([-3, 5, 0, -1, 5, -3]));// Output: [-3, -3, -1, 0, 5, 5]When normalizing, find min and max once at the start. Using different offsets during counting and output phases corrupts the result. This is a common implementation bug.
Understanding when counting sort should not be used is as important as knowing when it excels. The limited range property can fail in several ways, each demanding a different response.
Ask two questions: (1) Can values be directly used as array indices? (2) Is k ≤ n (or at least O(n))? If both answers are yes, counting sort is likely optimal. Otherwise, consider radix sort, bucket sort, or comparison-based alternatives.
Counting sort's complexity is O(n + k), where n is the input size and k is the range. This two-variable complexity requires careful analysis—you can't simply say 'counting sort is O(n)'.
12345678910111213141516171819202122232425262728293031
Counting Sort Complexity: O(n + k)═══════════════════════════════════ Phase 1: Initialize count array of size k → O(k) operations Phase 2: Count occurrences (iterate through input) → O(n) operations Phase 3: Compute cumulative counts → O(k) operations Phase 4: Build output array (iterate through input) → O(n) operations Total: O(k) + O(n) + O(k) + O(n) = O(n + k) ═══════════════════════════════════ Space Complexity: O(n + k) • Count array: O(k) • Output array: O(n) • Total auxiliary: O(n + k) ═══════════════════════════════════ Simplification Cases: • k = O(n) → O(n + n) = O(n) [Linear!] • k = O(1) → O(n + 1) = O(n) [Even better!] • k = n² → O(n + n²) = O(n²) [Quadratic...] • k = 2ⁿ → Exponential [Disaster]When k is a known constant (like k = 256 for byte values), we can simplify O(n + k) to O(n). But in algorithm analysis and competitive programming, always state the full O(n + k) complexity unless k is explicitly bounded.
The limited range property is the gateway to linear-time sorting. Before applying counting sort, you must verify this precondition and understand its implications.
You now understand the fundamental precondition for counting sort: the limited range property. This insight—that bounded, discrete values can be sorted without comparison—is the conceptual breakthrough that enables all non-comparison sorting algorithms. Next, we'll explore exactly how counting sort leverages this property through its counting phase.