---
title: "Counting Sort"
description: "Prefix sums turn counts into addresses"
source: https://vizlearn.app/algorithms/sorting/counting-sort
access: premium (interactive player requires Lifetime; this doc is free)
---

# Counting Sort

Counting sort is a non-comparison sorting algorithm for integer keys in a
known range 0..k. It tallies how many times each key occurs, converts the
tallies into positions with a prefix sum, then writes every element directly
into its final slot — O(n + k) time, O(n + k) extra space, and stable.

Here is the trick in one sentence: if you know how many keys are *smaller
than or equal to* yours, you know exactly where you belong — no need to
compare yourself with anyone. It works like a seating chart for a wedding.
You don't seat guests by asking each pair who outranks whom; you count the
RSVPs per family, run a quick running total to find where each family's block
of seats starts, and then walk guests straight to their chairs. Counting sort
never compares two elements. Not once.

## Counting Sort Turns Counts into Addresses

The algorithm is three loops, and each one is doing something different with
the same little array.

First, the **tally**. Walk the input once and increment `count[v]` for every
element `v`. When this loop ends, `count` is a histogram: `count[3] = 3`
means the key 3 appears three times. The element itself is only ever used as
an *index* into the count array — that is the whole non-comparison move.

Second, the **prefix sum**. Sweep the count array left to right, adding each
cell into the next: `count[i] += count[i - 1]`. This is the beat where the
array changes meaning under your feet. Before the sweep, `count[3]` said
"there are three 3s." After it, `count[3]` says "seven keys are ≤ 3" — which
is the seating-chart fact: the block of 3s *ends* at position 6, because
seven guests sit at or before it. Same cells, new units: counts became
addresses.

## The Backward Walk Keeps Counting Sort Stable

The third loop is the **placement**. Allocate the output array, then walk the input
*backward*. For each element `v`, decrement `count[v]` and write `v` at
`out[count[v]]`. One subtraction, one write, straight to the final position.
No probing, no shifting, no second look.

Why backward? Stability. After the prefix pass, `count[v]` points one past
the *last* slot reserved for `v`. The backward walk meets the last `v` in the
input first and gives it that last slot; the next-to-last `v` gets the slot
to its left, and so on. Equal keys land right to left exactly as the input
listed them right to left — original order preserved. Run the same loop
forward and every value still lands in the correct block, but equal keys come
out reversed. The array looks sorted; the stability is quietly gone. This
matters beyond aesthetics: radix sort runs a counting sort per digit and is
only correct because each pass is stable.

## Counting Sort Step by Step

The visualization runs `[2, 5, 3, 0, 2, 3, 0, 3]` — eight keys, k = 5, with
enough duplicates that stability is visible. Equal keys wear small badges
(3ᵃ, 3ᵇ, 3ᶜ in input order) so you can watch order survive.

1. **Tally.** The scan visits each element left to right and bumps its cell:
   the two 0s make `count[0] = 2`, the two 2s make `count[2] = 2`, the three
   3s make `count[3] = 3`, the lone 5 makes `count[5] = 1`. Result:
   `count = [2, 0, 2, 3, 0, 1]`.
2. **Prefix sum.** Left to right, each cell absorbs its neighbor:
   `[2, 2, 4, 7, 7, 8]`. Read `count[3] = 7` as "seven keys ≤ 3."
3. **Place 3ᶜ.** The backward walk starts at `arr[7] = 3`. Decrement
   `count[3]` from 7 to 6, write `out[6] = 3`. The last 3 takes the last slot
   of the 3-block.
4. **Place 0ᵇ.** `arr[6] = 0`: `count[0]` drops 2 → 1, so `out[1] = 0`.
5. **Place 3ᵇ.** `arr[5] = 3`: `count[3]` drops 6 → 5, so `out[5] = 3` —
   one slot *left* of 3ᶜ. That is stability happening in real time.
6. The remaining five placements repeat the pattern: 2ᵇ → `out[3]`,
   0ᵃ → `out[0]`, 3ᵃ → `out[4]`, 5 → `out[7]`, 2ᵃ → `out[2]`. Output:
   `[0, 0, 2, 2, 3, 3, 3, 5]`, badges reading a-b-c inside every block.

On the canvas, the count row sits between input and output because it is
literally the middleman: watch a `+1` pulse drop into a cell during the
tally, the row's label flip from *count* to *addresses* after the prefix
sweep, and each card fly through its address cell to the output slot it
computed. When a duplicate lands, the status line names the moment and a
green bracket gathers the equal-key block below the output — badges reading
in input order, the proof that stability held.

## Time and Space Complexity

| Case | Time |
| --- | --- |
| Best | O(n + k) |
| Average | O(n + k) |
| Worst | O(n + k) |

Space is O(n + k): the output array plus one count cell per possible key.
Counting sort is stable and not in-place, and its time complexity does not
depend on the input's initial order at all — a sorted input costs exactly the
same as a shuffled one.

The fine print is the k. Those bounds are a bargain while k stays near n, and
a disaster when it doesn't: sorting four values spread across keys 0..29
allocates 30 cells and drags the prefix sweep through 29 of them — the
*Scenarios* panel ships exactly that input so you can feel O(k) in the
scrubber. Push k to a billion and the count array is a billion cells for the
same four elements. That, in one array, is why comparison sorts still exist.
(The visualization caps keys at 30 — a canvas budget, not a property of the
algorithm.)

## Edge Cases

- **Empty array.** `max(arr)` has nothing to take a max of and throws; real
  implementations guard for it first. The visualization requires at least one
  element.
- **Single element.** One tally, one placement. The prefix sweep still runs
  over the key range below it.
- **All keys equal.** One hot cell holds the whole count; the output fills
  from a single address counting down, badges in input order.
- **All zeros.** k = 0, so the prefix loop runs zero times — the tally is
  already the address book.
- **k much larger than n.** Correct but wasteful; see the fine print above.

## Common Mistakes

- **Walking the final loop forward.** The output is still sorted, so tests
  that only check order will pass — while equal keys silently reverse. Sort
  records by key instead of bare integers and the bug surfaces immediately.
- **Writing before decrementing.** After the prefix pass, `count[v]` is one
  *past* the last slot for `v`. Write first and you overflow the block by
  one; the decrement-then-write order is load-bearing.
- **Sizing the count array by n.** It needs k + 1 cells, one per possible
  key — `max(arr) + 1`, not `len(arr)`. The two agree just often enough in
  toy tests to hide the bug.
- **Feeding it the wrong keys.** Negative integers need an offset shift
  first, and floats or strings have no count cell at all. Counting sort is
  an integer-keys specialist, not a general-purpose sort.