Counting Sort

Counting sort is a non-comparison sorting algorithm that sorts integers (or items keyed by integers) in O(n + k) time and O(n + k) space, where n is the number of items and k is the range of possible key values. Because it never compares two elements directly — it just counts how many times each key value occurs and uses arithmetic on those counts to compute final positions — it bypasses the Ω(n log n) comparison-sort lower bound. When k = O(n), counting sort is genuinely linear time. The catch: when k is much larger than n (e.g., sorting 1000 32-bit integers, where k = 2³² ≈ 4 billion), the O(k) cost dominates and counting sort becomes useless. So counting sort shines for small bounded-range integer keys: bytes (k=256), small enums, ages, percentage scores, day-of-year, or as a stable subroutine inside Radix Sort, which uses it to sort one digit at a time.

1. Intuition — Counting Hands at a Lecture

Imagine you’re a teacher with 200 students and you want to sort their final grades — each grade an integer from 0 to 100 — in ascending order.

• The naive approach: take each student’s grade, write it on a card, then sort the 200 cards. That’s O(n log n) with comparisons.
• The clever approach: walk down the line of students and ask each one their grade. Tally — keep a list count[0..100] and increment count[g] for each grade g. After the walk, count[g] is the number of students who got exactly grade g.
• Now you can construct the sorted output by enumerating: write down count[0] zeros, then count[1] ones, then count[2] twos, …, up through count[100] hundreds. That’s the sorted list.
• For a stable sort that preserves which student got each grade (not just the grade values), use a prefix-sum trick: convert count[] into a “starting index” array, then walk the input again placing each student at the correct position.

The key insight: if you know in advance there are only 101 possible values, you don’t need to compare anything. You can compute each item’s final position by counting. The sort is driven by arithmetic on counts, not by comparison decisions.

2. Tiny Worked Example (n = 8, k = 6)

Sort [2, 5, 3, 0, 2, 3, 0, 3] (each value is in [0, 5]).

Step 1: Count occurrences

Build count[0..5] by walking the input.

After walk: count = [2, 0, 2, 3, 0, 1]
                      0  1  2  3  4  5

Two 0s, zero 1s, two 2s, three 3s, zero 4s, one 5.

Step 2: Prefix-sum the count array (in-place)

Convert count[i] into “the number of elements with key ≤ i”. This will be the exclusive end position of each key’s group in the output.

Before: [2, 0, 2, 3, 0, 1]
Step 1:  count[1] += count[0]  → [2, 2, 2, 3, 0, 1]
Step 2:  count[2] += count[1]  → [2, 2, 4, 3, 0, 1]
Step 3:  count[3] += count[2]  → [2, 2, 4, 7, 0, 1]
Step 4:  count[4] += count[3]  → [2, 2, 4, 7, 7, 1]
Step 5:  count[5] += count[4]  → [2, 2, 4, 7, 7, 8]

So now count[0] = 2 means “after sorting, items with key 0 occupy slots 0 and 1 (total 2 items ≤ 0)”. count[3] = 7 means “items with key ≤ 3 occupy slots 0..6 (total 7 items)”.

Step 3: Build output by scanning input right-to-left

For each input element x, decrement count[x] and place x at index count[x] in the output. Right-to-left ensures stability — equal elements appear in the output in the same relative order as in the input.

Iterate from index 7 down to 0 of the input [2, 5, 3, 0, 2, 3, 0, 3]:

i	input[i]	count[input[i]] before	place at index	count[input[i]] after	output state
7	3	7	6	6	[_,_,_,_,_,_,3,_]
6	0	2	1	1	[_,0,_,_,_,_,3,_]
5	3	6	5	5	[_,0,_,_,_,3,3,_]
4	2	4	3	3	[_,0,_,2,_,3,3,_]
3	0	1	0	0	[0,0,_,2,_,3,3,_]
2	3	5	4	4	[0,0,_,2,3,3,3,_]
1	5	8	7	7	[0,0,_,2,3,3,3,5]
0	2	3	2	2	[0,0,2,2,3,3,3,5]

Final: [0, 0, 2, 2, 3, 3, 3, 5]. Sorted, stable, with zero comparisons between input elements.

Total work: one pass to count, one pass over the count array to prefix-sum, one pass to place. Grand total: O(n + k).

3. Pseudocode

counting_sort(arr, k):                            # k = max value + 1 (or known range)
    n := length(arr)
    count := array of zeros, length k
    output := array of length n

    # Phase 1: count occurrences
    for x in arr:
        count[x] := count[x] + 1

    # Phase 2: prefix sum → "exclusive end position" of each value
    for i from 1 to k - 1:
        count[i] := count[i] + count[i - 1]

    # Phase 3: place elements right-to-left for stability
    for i from n - 1 down to 0:
        x := arr[i]
        count[x] := count[x] - 1
        output[count[x]] := x

    return output

The right-to-left iteration in Phase 3 is what makes counting sort stable. If you scan left-to-right with the same prefix-sum interpretation, you reverse the order of equal elements (still sorted, but unstable). For the algorithm-as-subroutine inside Radix Sort, stability is non-negotiable; right-to-left scanning is the standard.

4. Python Implementation

def counting_sort(arr: list[int], k: int | None = None) -> list[int]:
    """Sort `arr` using counting sort.
    `k` is one more than the maximum value (the size of the count array).
    If not provided, it's inferred — adding one O(n) pass.
    Returns a new sorted list. Stable.
    """
    if not arr:
        return []
    if k is None:
        k = max(arr) + 1
    n = len(arr)
 
    # Phase 1: count occurrences
    count = [0] * k
    for x in arr:
        count[x] += 1
 
    # Phase 2: prefix sum
    for i in range(1, k):
        count[i] += count[i - 1]
 
    # Phase 3: place elements right-to-left for stability
    output = [0] * n
    for i in range(n - 1, -1, -1):
        x = arr[i]
        count[x] -= 1
        output[count[x]] = x
 
    return output

For sorting records keyed by integers (the typical case where stability matters):

def counting_sort_by_key(records: list, key, k: int) -> list:
    """Stably sort `records` by `key(record)` ∈ [0, k)."""
    n = len(records)
    count = [0] * k
    for r in records:
        count[key(r)] += 1
    for i in range(1, k):
        count[i] += count[i - 1]
    output = [None] * n
    for i in range(n - 1, -1, -1):
        k_i = key(records[i])
        count[k_i] -= 1
        output[count[k_i]] = records[i]
    return output

This variant is what Radix Sort uses internally for each digit position — stability ensures the sort by digit d+1 doesn’t undo the sort by digit d.

5. Complexity

5.1 Time

• Phase 1 (count): one pass over arr, O(n) work.
• Phase 2 (prefix sum): one pass over count, O(k) work.
• Phase 3 (place): one pass over arr, O(n) work.
• Total: O(n + k).

When k = O(n) — i.e., the value range is bounded by a constant times the number of items — counting sort runs in linear time: O(n). This includes natural cases like sorting bytes (k = 256), sorting school grades (k = 101), or sorting 32-bit integers when n ≥ 2³² / c for some constant c (rarely the case in practice).

When k = ω(n) — the value range is asymptotically larger than n — counting sort becomes worse than O(n log n) comparison sorts. Sorting 1000 random 32-bit integers (k ≈ 4 × 10⁹) with counting sort would take billions of operations to clear an essentially-empty count array. Don’t use counting sort for unbounded or large-range integers. Use Quicksort / Tim Sort instead, or use Radix Sort (which decomposes large integers into digit-position counting sorts with small k per pass).

5.2 Why Counting Sort Beats the Ω(n log n) Lower Bound

Any comparison-based sorting algorithm — one that decides what to do based only on the result of comparisons a < b between input elements — must do Ω(n log n) comparisons in the worst case. The proof: model the algorithm as a decision tree in which each internal node is a single comparison and each leaf is a permutation of the input. There are n! distinct permutations, so the tree has at least n! leaves. The worst-case running time is at least the tree’s depth, which is at least ⌈log₂(n!)⌉ = Θ(n log n) by Stirling’s approximation:

log₂(n!) = log₂(1) + log₂(2) + ... + log₂(n)
         ≥ (n/2) · log₂(n/2) = Θ(n log n)

This bound applies only to algorithms that learn about the input by comparing pairs of elements. Counting sort doesn’t compare elements at all. It uses each input value as an array index — an O(1) operation that extracts a log₂(k)-bit piece of information about the element in one step, while a single comparison only extracts 1 bit (a < b: yes or no).

By directly indexing into a k-sized count array, counting sort effectively uses a much richer query than comparison. The “lower bound” doesn’t apply because the model is different. This is a clean illustration of how the computational model assumed in a lower bound matters as much as the bound itself.

Subtle: the lower bound is per element, not per algorithm

The Ω(n log n) bound says “any comparison sort needs n log n comparisons in the worst case.” It does not say “any sorting algorithm needs n log n operations.” Counting sort (and Radix Sort, and bucket sort) sidestep the bound because they use input values as more than just opaque comparable objects — they use them as integers/keys with internal structure.

5.3 Space

• count array: O(k).
• output array: O(n).
• Total auxiliary: O(n + k).

This is counting sort’s main weakness alongside the k cost: it is not in-place. You always need a separate output buffer because Phase 3 cannot overwrite the input safely (you’d corrupt elements you haven’t yet processed). For workloads where memory is tight, use Heap Sort (O(1) aux) or in-place Quicksort (O(log n) stack).

6. Stability

Counting sort is stable when implemented with the right-to-left placement scan in Phase 3. Equal elements appear in the output in the same relative order as in the input.

This stability is essential for counting sort’s role as a subroutine inside Radix Sort. Radix sort processes one digit at a time (least-significant first, in the LSD variant); each per-digit sort must be stable so that prior-digit ordering is preserved within ties on the current digit. Without stability, radix sort would produce nonsense — you’d lose the lower-digit information after each higher-digit pass.

If you reverse the direction of Phase 3 (left-to-right with the same prefix-sum interpretation), you get a perfectly correct sort with reversed stability — equal elements appear in reverse input order. Some implementations do this when using counting sort with negative-direction radix sort or other backwards conventions, but the standard pattern is right-to-left for forward stability.

7. Variants and Adjustments

7.1 Negative Numbers

Counting sort indexes by value, so it can’t directly handle negative integers. Two common fixes:

• Shift: find min(arr) = m, then index by x - m. Now indices range over [0, max - min]. This is a constant-time fix per element.
• Two passes: sort negatives and non-negatives separately, then concatenate. Less elegant.

def counting_sort_signed(arr: list[int]) -> list[int]:
    if not arr: return []
    lo, hi = min(arr), max(arr)
    k = hi - lo + 1
    count = [0] * k
    for x in arr:
        count[x - lo] += 1
    for i in range(1, k):
        count[i] += count[i - 1]
    output = [0] * len(arr)
    for i in range(len(arr) - 1, -1, -1):
        v = arr[i]
        count[v - lo] -= 1
        output[count[v - lo]] = v
    return output

7.2 Floating-Point Keys

Counting sort fundamentally cannot sort floats — there’s no finite k for the real numbers. Workarounds:

• Bucket sort — partition the float range into n buckets, sort each bucket with another sort, concatenate. Average O(n) for uniformly distributed floats.
• Bit reinterpretation — treat the IEEE 754 bit pattern as an integer and use Radix Sort; works for non-negative floats with a sign-bit trick for negatives.

7.3 Sorting by Key With Larger Records

When sorting structured records (not just integers), the count-and-place pattern still works — you key on an integer-valued field. Memory cost is O(n) for the output array of records plus O(k) for the count array. No comparison of records ever happens.

7.4 In-Place Variant

A truly in-place counting sort is possible when you only need to count and rewrite, not preserve original element identity. For example, if arr contains only integers in [0, k) and you don’t need stability, you can simply:

def counting_sort_inplace(arr: list[int], k: int) -> None:
    count = [0] * k
    for x in arr:
        count[x] += 1
    idx = 0
    for v in range(k):
        for _ in range(count[v]):
            arr[idx] = v
            idx += 1

This is O(n + k) time, O(k) space, and stable in the trivial sense (since identity isn’t preserved, “stability” isn’t meaningful — equal elements are indistinguishable). But this only works for primitive integer arrays; you cannot use it to sort records by an integer key, because once you discard the original array’s identity you’ve lost the rest of each record.

8. When To Use Counting Sort

8.1 Use it when

• Keys are integers in a small bounded range (e.g., k ≤ 10n).
• Stability matters and you can afford O(n) extra space.
• You’re implementing the inner sort of Radix Sort.
• You’re solving a problem with naturally-bounded keys: histogram queries, age sorting, ASCII characters, DNA bases (k = 4), small enums.

8.2 Don’t use it when

• Keys are large integers (e.g., 32-bit or 64-bit unrestricted) — use Radix Sort (which internally uses counting sort but with small per-digit k) or comparison sorts.
• Keys are floats or strings — counting sort doesn’t apply directly. Use bucket sort or radix sort respectively.
• Memory is tight — counting sort needs O(n + k) aux. Use Heap Sort or Quicksort.
• k >> n (huge sparse range with few items) — the O(k) cost dwarfs O(n). Counting sort is wasteful.

8.3 The Killer Application: Radix Sort

The most important use of counting sort in modern code is inside Radix Sort. Radix sort takes a list of n d-digit integers in base b and sorts them in O(d × (n + b)) time by performing d stable passes, each sort by a single digit, using counting sort with k = b. Pick b = O(n) and d = O(1) (for fixed-width keys like 32-bit integers, d = 4 for b = 256), and you get O(n) total — beating the comparison-sort lower bound at scale. Counting sort’s stability is what makes the multi-pass radix sort produce the right final order.

9. Pitfalls

9.1 Choosing the Wrong k

If you set k too small, you’ll write past the end of count (or worse, silently miscount). If you set k much too large (e.g., k = 2³² for a small array of 32-bit integers), you waste O(k) time and memory zeroing the count array. Always size k to the actual range of input values (or use max(arr) + 1 if unknown), or know the domain bound a priori.

9.2 Forgetting to Iterate Right-to-Left for Stability

Iterating Phase 3 left-to-right with the same prefix-sum interpretation produces a sorted but unstable output (equal elements reversed). When using counting sort inside Radix Sort this is a correctness bug — the radix sort will produce wrong results. Always scan from n - 1 down to 0.

9.3 Off-by-One in the Prefix Sum Interpretation

The prefix-summed count[i] represents the exclusive end position of value i in the sorted output (or equivalently, the count of elements ≤ i). This is why you decrement count[x] before placing in Phase 3 (turning the exclusive end into the actual placement index). Getting this off-by-one writes one slot past the end or leaves slot 0 unused.

9.4 Treating It As a “General Purpose Sort”

Counting sort is not a general sort — it requires bounded integer-valued keys. Trying to use it for arbitrary comparable objects, or for floating-point numbers, or for huge ranges, defeats its purpose and produces either bugs or terrible performance.

9.5 Ignoring Negative Numbers

Vanilla counting sort indexes by value, so arr[-3] would index count[-3], which Python silently allows (treating as count[k - 3]) but is semantically wrong. Always offset by min(arr) if negatives are possible.

9.6 Modifying count In-Place Then Trying to Reuse It

After Phase 3, the count array’s values have been decremented to zero (or near-zero); they’re no longer the prefix-sum end-positions. If you need them again, save a copy.

10. Diagram — The Three-Phase Pipeline

flowchart TD
    Input["Input: arr=[2,5,3,0,2,3,0,3], k=6"] --> P1["Phase 1: Count<br/>count=[2,0,2,3,0,1]"]
    P1 --> P2["Phase 2: Prefix sum<br/>count=[2,2,4,7,7,8]<br/>Now count[i] = #elements ≤ i"]
    P2 --> P3["Phase 3: Place right-to-left<br/>For each arr[i] from end:<br/>  count[arr[i]] -= 1<br/>  output[count[arr[i]]] = arr[i]"]
    P3 --> Output["Output: [0,0,2,2,3,3,3,5]<br/>Sorted, stable, zero comparisons"]

What this diagram shows. Counting sort’s three sequential phases. Phase 1 builds a histogram of input values — each input element contributes +1 to count[value]. Phase 2 turns the histogram into a cumulative histogram via prefix sum: count[i] becomes the number of input elements with value ≤ i, which is exactly the exclusive end index of value i’s group in the sorted output. Phase 3 walks the input in reverse order (for stability), placing each element at the position one before the current count[value], then decrementing — so that the next equal-valued element will be placed one slot earlier, preserving input order among equal keys. Crucially, no two input elements are ever compared with each other; the entire sort is driven by counts and array indices. This is why counting sort beats the Ω(n log n) comparison-sort lower bound: the lower bound applies only to algorithms that learn about input via comparison, and counting sort learns by direct indexing instead.

11. Common Interview Problems

Problem	Counting Sort Connection
”Sort an array of integers in [0, 100]”	Direct application — O(n + 100) = O(n).
”Sort an array of student records by integer grade, stably”	Counting sort by key, with stable Phase 3.
”Find the median of n integers, all in a small range”	Counting sort + walk-cumulative-counts to find the n/2-th.
”Implement Radix Sort”	Counting sort is the inner per-digit sort.
”Why can counting sort be O(n) when no comparison sort can?”	Decision-tree lower bound applies only to comparison-based algorithms; counting sort uses values as indices.
”Sort an array where each value occurs O(1) times and the range is huge”	Counting sort is wrong here — O(k) dominates. Use a comparison sort or a hash-based approach.

12. Open Questions

• What’s the largest k/n ratio at which counting sort still beats Quicksort in practice on modern hardware? Cache effects favor counting sort at moderate k due to predictable access patterns.
• Can a parallel/SIMD counting sort be made significantly faster than scalar? Yes for Phase 1 (atomic increments or per-thread histograms), tricky for Phase 3 (write-coordination).
• Is bucket sort just “counting sort with float keys”? Approximately yes — bucket sort is the float-keyed cousin, with the same O(n) average for uniformly-distributed inputs.

13. See Also

• Radix Sort — uses counting sort as its per-digit subroutine
• Merge Sort — comparison-based, stable, O(n log n) always
• Quicksort — comparison-based, in-place, O(n log n) average
• Heap Sort — comparison-based, O(1) aux, O(n log n) worst
• Tim Sort — Python/Java’s adaptive comparison sort
• Insertion Sort — small-n baseline; comparison-based
• Big-O Notation
• SWE Interview Preparation MOC