Counting Sort
Imagine sorting one million exam scores, each an integer between 0 and 100. A comparison-based sort like Merge Sort would spend time proving pairwise orderings. In a real sense, these comparisons are unnecessary — you already know every possible value the keys can take. Counting Sort exploits this: instead of comparing elements, it counts them. It uses the keys themselves as indices into an array. This single shift in perspective breaks through a wall that no comparison sort can cross. The wall is The Comparison-Sort Lower Bound. It proves that any algorithm relying solely on element-to-element comparisons must take Ω(n log n) time in the worst case. Counting Sort sidesteps this bound entirely by never comparing two elements against each other. It instead asks "how many elements are less than or equal to this value?" This question is answerable directly from counts, in linear time, when the range of possible key values is small. This matters far beyond academic curiosity. Counting Sort is the quiet workhorse inside histogram equalization in image processing. It also powers bucket-based grade or age reports. Most importantly, it serves as the stable subroutine that makes Radix Sort possible. Radix Sort sorts multi-digit numbers one digit at a time. It only works correctly if the per-digit sorting step preserves the relative order of equal keys from the previous pass. That preservation property, called stability, is not a minor implementation detail. It is the mathematical linchpin of the entire radix sorting strategy. Counting Sort must be built to guarantee it. This article gives a precise, correct derivation of Counting Sort. It covers the counting and prefix-sum mechanics that place each element in its final position. It explains why the placement must proceed in a specific direction to preserve stability. It includes the Θ(n + k) complexity analysis, and a full worked trace on non-trivial data. Finally, it covers the historical and practical context that connects it to radix sorting and to the comparison-sort lower bound it circumvents.
- Counting Sort sorts n integers with keys in a small range [0, k] in Θ(n + k) time, beating the Ω(n log n) comparison-sort barrier by not comparing elements at all.
- It works by counting occurrences of each key, converting counts into prefix sums (positions), and placing elements directly into a sorted output array.
- Correctly implemented, it is stable: elements with equal keys retain their original relative order — a property essential for Radix Sort.
- Stability requires iterating the input from last to first during placement, using pre-computed prefix-sum positions.
- Space cost is Θ(n + k); when k is much larger than n, the algorithm becomes impractical despite its linear time claim.
- Counting Sort is not a general-purpose sort — it assumes small, known-range integer (or integer-mappable) keys, unlike comparison sorts which need no such assumption.
Counting Sort sorts by counting how many elements belong at or before each key value, then uses those counts as direct array indices — trading comparisons for arithmetic on the key range.
The idea
Counting Sort is a non-comparison sort: it never asks "is a < b?" for two elements a and b. Instead, it assumes every key is an integer drawn from a known, bounded range {0, 1, ..., k}, and it determines each element's final sorted position by counting. Specifically, for a value v, the number of elements less than or equal to v tells you exactly how many array slots precede the last occurrence of v in sorted order. This is a purely arithmetic computation on frequency counts — no pairwise comparisons required. The algorithm proceeds in three conceptual phases. First, build a frequency array C where C[v] counts how many input elements equal v. Second, transform C into a prefix-sum array, so that C[v] now holds the count of elements with key ≤ v — this value is precisely the rank (1-indexed count) of the last such element in the final sorted output. Third, place each input element into its correct output slot using C as a position table, decrementing C[v] after each placement so that the next element with key v lands just before the previous one. A crucial refinement distinguishes a merely correct Counting Sort from a useful one: stability. A sort is stable if elements with equal keys appear in the output in the same relative order they had in the input. Counting Sort achieves this only if the placement phase scans the input array from last index to first, using the decrementing prefix-sum trick. Scanning forward while decrementing would reverse the relative order of equal keys, silently breaking stability while still producing a "sorted" array. This distinction matters enormously because Radix Sort sorts numbers digit by digit from least significant to most significant, and it is only correct if each digit's sorting pass is stable — otherwise, the ordering established by earlier (less significant) digit passes gets destroyed by later passes.
How it works
Let the input be an array `A[1..n]` with each key `A[i]` an integer in the range `[0, k]`. We produce a sorted output array `B[1..n]` and use an auxiliary count array `C[0..k]`.
Phase 1 — Count occurrences. For each element in A, increment the corresponding bucket in C.
Phase 2 — Prefix sums. Convert C so that `C[v]` = number of elements ≤ v. This is done by accumulating: `C[v] += C[v-1]`.
Phase 3 — Stable placement. Scan A from the last element to the first. For each `A[i]`, place it at output position `C[A[i]]`, then decrement `C[A[i]]` by 1. Placing at position `C[A[i]]` uses the current prefix-sum count as a 1-indexed slot; decrementing ensures the next element with the same key (which, scanning backward, is an earlier element in A) lands one slot to the left, preserving input order among equal keys. ``` COUNTING-SORT(A, n, k):
# A: input array, 1-indexed, values in [0, k]
# n: length of A
# k: maximum possible key value
# returns B: sorted, stable output array let C[0..k] be a new array, initialized to 0 let B[1..n] be a new array
# Phase 1: count occurrences of each key for i = 1 to n: C[A[i]] = C[A[i]] + 1
# Phase 2: transform counts into prefix sums
# C[v] now equals the number of elements with key <= v for v = 1 to k: C[v] = C[v] + C[v - 1]
# Phase 3: place elements, scanning input BACKWARD for stability for i = n downto 1: B[C[A[i]]] = A[i] C[A[i]] = C[A[i]] - 1 return B ``` Each phase is a single linear pass: Phase 1 is Θ(n), Phase 2 is Θ(k), Phase 3 is Θ(n). No element is ever compared to another; every decision uses `A[i]` purely as an array index.
Complexity & correctness
Time complexity. Phase 1 iterates over all n input elements: Θ(n). Phase 2 iterates over the k+1 possible key values: Θ(k). Phase 3 iterates over all n input elements again: Θ(n). The total is Θ(n) + Θ(k) + Θ(n) = Θ(n + k). This bound is tight in every case — best, average, and worst-case time are all Θ(n + k), because the algorithm always performs exactly these three full passes regardless of the input's actual arrangement. There is no early termination and no input-dependent branching that changes the asymptotic work.
Why this doesn't contradict the comparison-sort lower bound. The Comparison-Sort Lower Bound proves that any sorting algorithm making decisions solely via pairwise comparisons must take Ω(n log n) time, via a decision-tree argument: n! possible orderings require a decision tree of depth Ω(log(n!)) = Ω(n log n). Counting Sort escapes this bound because it is not a comparison-based algorithm at all — it uses key values as direct memory addresses, extracting information via arithmetic indexing rather than binary comparisons. When k = O(n), the algorithm runs in Θ(n) time, which would be impossible for a comparison sort but is perfectly consistent with the lower bound because that bound simply does not apply to non-comparison models.
Space complexity. The algorithm uses Θ(k) space for the count array and Θ(n) space for the output array, for a total of Θ(n + k) auxiliary space (beyond the input). This is not an in-place sort.
Correctness — invariant and proof sketch. The key claim is: After Phase 2, for every key value v, C[v] equals the number of input elements with key ≤ v. This is immediate by induction on Phase 1 (each C[v] correctly counts occurrences of v) followed by the standard prefix-sum recurrence in Phase 2: C[v] = C[v] + C[v-1] accumulates counts of all keys ≤ v, with base case C[0] unchanged since there is no key < 0 to add. Given this invariant, in Phase 3, when we process `A[i] = v`, the current value of `C[v]` is exactly the position (1-indexed) that the next unplaced element with key v should occupy, because:
- Elements with key < v occupy all positions before the current count of key-v elements placed so far.
- Elements with key = v occupy a contiguous block, and `C[v]` tracks how many of that block remain to be placed, counted from the right end of the block inward.
Why backward scanning gives stability. Suppose two elements `A[i]` and `A[j]` both have key v, with i < j (so `A[i]` appears earlier in the input). Scanning from n down to 1, we encounter `A[j]` before `A[i]`. We place `A[j]` at position `C[v]`, then decrement C[v]. When we later reach `A[i]`, we place it at position `C[v] - 1` — one slot to the left of where `A[j]` went. Since smaller output index means earlier in the sorted array, `A[i]` ends up before `A[j]` in B, exactly matching their relative input order. This is precisely the stability guarantee. If instead we scanned forward (i = 1 to n) while still decrementing C, the earlier element `A[i]` would be placed first at the rightmost slot of the key-v block, and the later element `A[j]` would land to its left — reversing their relative order and breaking stability.
The tradeoff. Counting Sort's Θ(n + k) bound is only useful when k = O(n) (or close to it). If keys range over, say, all 32-bit integers (k ≈ 4 × 10⁹) but n = 1000, the count array alone would dwarf any benefit, making the algorithm far worse than an Θ(n log n) comparison sort in practice. Counting Sort is a specialist tool: powerful precisely when the key range is small relative to n, and it is this constraint that motivates Radix Sort, which applies Counting Sort digit-by-digit so that k is bounded by the digit base (e.g., 10 or 256) rather than by the full magnitude of the numbers.
Worked example
Sort the array `A = [4, 1, 3, 4, 3]` (n = 5, keys range over [0, k] with k = 4). To make stability visible, imagine each `4` and `3` is tagged with a subscript marking its original position: `4ₐ, 1, 3ₐ, 4ᵦ, 3ᵦ` (subscripts are for tracking only — the sort algorithm sees no such labels, only the numeric keys).
Phase 1 — count occurrences:
| v | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| C[v] | 0 | 1 | 0 | 2 | 2 |
Phase 2 — prefix sums (C[v] += C[v-1]):
| v | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| C[v] | 0 | 1 | 1 | 3 | 5 |
This says: 0 elements are ≤ 0; 1 element is ≤ 1; 1 element is ≤ 2; 3 elements are ≤ 3; 5 elements are ≤ 4 (all of them, correctly, since n=5).
Phase 3 — backward placement, tracing i = 5 down to 1:
| Step | i | A[i] | C[A[i]] before | Action | C[A[i]] after |
|---|---|---|---|---|---|
| 1 | 5 | 3ᵦ | 3 | B[3] = 3ᵦ | 2 |
| 2 | 4 | 4ᵦ | 5 | B[5] = 4ᵦ | 4 |
| 3 | 3 | 3ₐ | 2 | B[2] = 3ₐ | 1 |
| 4 | 2 | 1 | 1 | B[1] = 1 | 0 |
| 5 | 1 | 4ₐ | 4 | B[4] = 4ₐ | 3 |
Resulting B (reading B[1] through B[5]): `1, 3ₐ, 3ᵦ, 4ₐ, 4ᵦ`. Observe stability directly: the two `3`s appear as `3ₐ` then `3ᵦ` — matching their original relative order in A (3ₐ was at index 3, 3ᵦ at index 5, and 3ₐ preceded 3ᵦ in the input). Likewise the two `4`s appear as `4ₐ` then `4ᵦ`, again preserving input order (4ₐ was at index 1, 4ᵦ at index 4). Had the algorithm scanned forward instead of backward while still decrementing, the output would have been `1, 3ᵦ, 3ₐ, 4ᵦ, 4ₐ` — correctly sorted by value, but with equal-key pairs reversed, silently violating stability. This distinction is invisible if you only check "is the output non-decreasing?" — you must check relative order among ties to catch it.
Common pitfalls & traps
| Pitfall | Why it happens | Consequence |
|---|---|---|
| Forward scan in Phase 3 | Seems symmetric/natural to mirror Phase 1's forward loop | Produces a correctly sorted array that is not stable — breaks Radix Sort silently |
| Off-by-one in prefix sums | Starting the accumulation loop at v=0 instead of v=1, double-counting C[0] | Miscomputes all subsequent positions, corrupting the whole output |
| Assuming negative keys work unmodified | Array indices can't be negative | Must offset all keys by `-min(A)` before counting, and offset back after |
| Using Counting Sort when k ≫ n | Blindly trusting "Θ(n+k) is linear" | Θ(k) dominates; can be slower and far more memory-hungry than an Θ(n log n) sort |
| Forgetting the output array is separate from input | Trying to sort "in place" like Insertion Sort | Counting Sort inherently needs Θ(n) extra space for B; it is not in-place |
| Confusing "sorted" with "stable" in testing | Test suites often only check monotonicity | Ties get silently reordered; bugs surface only downstream, e.g., in radix passes |
Pioneers & history
Counting Sort's core idea — using key values as direct indices for tabulation rather than comparing them — traces back to mechanical tabulating and census-processing techniques that predate modern computing, where physical card sorters grouped records by punched digit values. Its formalization as a stable, linear-time algorithmic primitive, and its central role in radix sorting, was consolidated in the algorithms literature of the mid-20th century as computer scientists systematically classified sorting methods by their comparison versus non-comparison structure.
Origins · 1 minHarold H. Seward and how this was discovered
Seward's 1954 MIT master's thesis on "Information Sorting in the Application of Electronic Digital Computers to Business Operations" is widely credited with the earliest rigorous treatment of radix sorting techniques and the counting-based bucket mechanism that makes each digit pass both efficient and stable. His work connected the practical punched-card sorting machines of the era — which processed one column of digits at a time — to a precise algorithmic description suitable for the emerging stored-program computer.
Where this matters
Counting Sort's most important real-world role is as the stable inner loop of Radix Sort, which is used to sort large collections of fixed-width keys — strings, IP addresses, suffix arrays in bioinformatics pipelines, and integer keys in database index construction — in linear time relative to the total number of digits processed. Because Radix Sort's correctness depends entirely on each digit pass being stable, any production radix-sort implementation must get the backward-scan discipline of Counting Sort exactly right. Beyond radix sorting, Counting Sort (or its close cousin, bucket-based counting) appears directly in histogram computation for image processing — computing per-intensity pixel counts for contrast/histogram equalization is literally the counting phase of Counting Sort. It shows up in GPU and parallel computing as a building block for stream compaction and parallel prefix-sum (scan) based sorting, where the prefix-sum phase of Counting Sort parallelizes naturally across many cores. It is also a natural fit whenever keys are small bounded categories — sorting exam grades (0–100), sorting by age bracket, or bucketing log-level severities — where k is known and small, making the Θ(n + k) bound genuinely linear and dramatically faster than a general comparison sort.
Ask the tutor: How does the choice of digit base in Radix Sort trade off the number of Counting Sort passes against the size of each pass's key range k?
Is Counting Sort a comparison sort?
No. Counting Sort never compares two input elements to each other; it only reads each element's key value and uses it as an index into a count array. This is exactly why it can escape the Ω(n log n) The Comparison-Sort Lower Bound, which applies strictly to algorithms whose only source of ordering information is pairwise comparisons. Counting Sort instead extracts ordering information from arithmetic on the key range itself — building a frequency table and then a prefix-sum table — which is a fundamentally different computational model, sometimes called an "index" or "distribution" sort.
Why does Counting Sort need the key range k to be small?
Because its time and space complexity are Θ(n + k): it allocates a count array of size k+1 and always performs a full pass over that range during the prefix-sum step. If k is small relative to n — say sorting exam scores from 0 to 100 with a million students — this is essentially linear, Θ(n). But if k is enormous (e.g., arbitrary 64-bit integers) while n is modest, the Θ(k) term dominates and can make Counting Sort slower and far more memory-hungry than a comparison sort like Merge Sort or Quicksort, despite the "linear time" label.
What does it mean for a sort to be "stable," and why does Counting Sort need extra care to achieve it?
A stable sort preserves the relative order of elements that compare equal — if two records have the same key, the one appearing first in the input still appears first in the output. Counting Sort's placement phase computes, for each key value, a single position from the prefix-sum table; naively applying this forward would place equal-key elements in reversed order. Scanning the input backward while decrementing the count table fixes this: later-appearing equal-key elements are placed into higher-index slots first, leaving earlier-appearing ones to correctly land at lower indices.
How does Counting Sort relate to Radix Sort?
Radix Sort sorts multi-digit keys by repeatedly applying a stable single-digit sort, processing digits from least significant to most significant. Counting Sort is the canonical choice for that single-digit sort because a digit's value range (e.g., 0–9 for base 10) is small and fixed, making each Counting Sort pass run in Θ(n + base) time. Because Radix Sort relies on each pass preserving the ordering established by previous, less-significant-digit passes, the stability of Counting Sort is not optional — it is the mathematical property that makes multi-pass digit sorting correct at all.
Can Counting Sort handle negative numbers or non-integer keys?
Directly, no — array indices must be non-negative integers. For negative integers, a simple fix works: find the minimum key value m in the input, then use `A[i] - m` as the index during counting and placement, effectively shifting the whole range to start at 0. For non-integer keys (floats, strings), Counting Sort cannot be applied directly unless there is a way to map keys to a small, bounded set of integer buckets — which is exactly the strategy used in Radix Sort for strings and fixed-precision numbers, and in general Bucket Sort variants.
How does Counting Sort's worst-case time compare to its best-case time?
They are identical: Θ(n + k) in all cases. Unlike comparison sorts such as Quicksort (which can degrade to Θ(n²) on adversarial input) or even Insertion Sort (Θ(n) best case on nearly sorted input, Θ(n²) worst case), Counting Sort performs exactly three fixed-structure passes — count, prefix-sum, place — regardless of the initial arrangement of the input. This predictability is a genuine advantage in latency-sensitive systems where worst-case guarantees matter more than average-case speed.
Is Counting Sort ever used as a general-purpose default sort, like Quicksort or Timsort?
Rarely as a standalone default, because its Θ(n + k) bound is only competitive when the key range k is known in advance and small relative to n — an assumption general-purpose library sorts cannot make about arbitrary user data. Instead, it is used deliberately in specialized contexts: as a subroutine inside Radix Sort for large-scale integer or string sorting, in histogram-based image processing, and in any pipeline where keys are naturally small bounded categories (grades, ages, byte values), where its guaranteed linear-time, stable behavior is a genuine win over general comparison-based sorts.