SortingAlgorithmaka count sort, histogram sort

Counting Sort

Count occurrences of each key in a small integer range, then place elements by prefix sums — linear time, no comparisons.

▶ VisualizePattern: HashingPractice (4)
Progress

Overview

Counting sort sorts integers (or anything with a small integer key) in O(n + k) where k is the size of the key range. It never compares elements: it tallies how many times each key appears, converts the tallies to starting positions with a Prefix Sum, and drops each element into its slot. This beats the Ω(n log n) lower bound because that bound applies only to comparison sorts.

The stable version (placing elements by iterating the input in order) is the building block of Radix Sort. It needs O(n + k) extra space, so it is only sensible when k is not much larger than n — sorting exam scores 0–100, ages, bytes, characters, or small enumerations.

non-comparisonO(n + k)stableinteger keyslinear time

Intuition

A mental model before the formal terms.

Sorting 10,000 exam papers by score 0–100: rather than comparing papers, set up 101 labelled piles and drop each paper on its pile in one pass. Then read the piles in order. The number of papers is irrelevant to how many piles you need.

How it works

  1. Find the key range [min, max]; let k = max - min + 1.
  2. Build count[0..k): for each element, count[key - min] += 1.
  3. Turn counts into positions: count[i] becomes the number of elements with key < i (exclusive prefix sum) — the starting index of key i in the output.
  4. Iterate the input left to right, placing each element at out[count[key]] and incrementing count[key]. Left-to-right placement makes the sort stable.
  5. For plain integers without satellite data, simply emit each key count[i] times.

Why it works

After the prefix sum, count[i] is exactly the number of elements with key less than i, which is the 0-based index where the first element with key i belongs in sorted order.

Placing elements in input order with an incrementing cursor per key preserves the original relative order of equal keys — stability.

Every step is a single pass over n elements or k buckets: O(n + k) time and space.

Recognition

How to tell a problem wants this.

  • Keys are integers in a small known range ("values between 0 and 1000", "ages", "characters a–z", "0/1/2 colors").
  • Constraints say n ≤ 10^6 with max value ≤ 10^6 — a comparison sort works but linear time is the intended answer.
  • You need a frequency histogram anyway (anagram checks, top-k by count).
  • A stable sort by a small key is required as a subroutine (Radix Sort, bucket by digit).
“have you seen this before” → Hashing“sum of subarray” → Prefix Sum

Interactive visualization

Play, step, change the input. ← → and space work too.

a
4
0
2
1
2
2
8
3
3
4
3
5
1
6
0
7
4
8
value
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
count
0
0
0
1
0
2
0
3
0
4
0
5
0
6
0
7
0
8
out
0
1
2
3
4
5
6
7
8
1/29Values range from 0 to k=8. Counting sort avoids comparisons entirely: it tallies how often each value occurs.
Element being processedCount slot updatedPlaced in output
PseudocodeLearn Counting Sort →
1k = max(a); count = [0] * (k+1)
2for x in a: count[x] += 1
3for v in 1 .. k: count[v] += count[v-1]   # prefix sums
4for x in reversed(a):
5  count[x] -= 1
6  out[count[x]] = x
7copy out into a
Variables
n9
k8
Complexity
best O(n + k)
avg O(n + k)
worst O(n + k)
space O(n + k)
Speed

Pseudocode

1mn, mx = min(a), max(a); k = mx - mn + 1
2count = [0] * k
3for x in a: count[x - mn] += 1
4pos = exclusive prefix sum of count
5for x in a (in order): out[pos[x - mn]] = x; pos[x - mn] += 1
6return out

Implementations

1def counting_sort(a: list[int]) -> list[int]:
2    if not a:
3        return []
41 · Find the key range
5    mn, mx = min(a), max(a)
6    k = mx - mn + 1
72 · Count occurrences of each key
8    count = [0] * k
9    for x in a:
10        count[x - mn] += 1
113 · Exclusive prefix sums: count[i] = number of elements < i + mn
12    total = 0
13    for i in range(k):
14        count[i], total = total, total + count[i]
154 · Place each element at its slot, left to right (stable)
16    out = [0] * len(a)
17    for x in a:
18        out[count[x - mn]] = x
19        count[x - mn] += 1
20    return out
Walkthrough
  1. min(a), max(a) are two C-speed passes; fine for clarity.
  2. [0] * k allocates the histogram; Python ints never overflow so counts are safe.
  3. The tuple assignment count[i], total = total, total + count[i] evaluates the right side first, producing exclusive prefix sums in one line.
  4. Placement in input order with a post-increment (count[...] += 1 after the write) is stable.
  5. A new list is returned; use a[:] = counting_sort(a) to sort in place.
Complexity (this implementation)
time O(n + k) · space O(n + k)

collections.Counter(a) builds the histogram in C, but iterating keys in sorted order costs O(k log k) unless you loop over range(mn, mx + 1).

Language notes
  • Counter + sorted(counter.items()) is the idiomatic key-only version when k is small.
  • For sorting records by key, sorted(a, key=...) is already stable and O(n log n); counting sort only wins when k is small relative to n.
  • Lists of ints are boxed objects in CPython; array.array('i') or NumPy (np.bincount) are far faster for big histograms.
Common mistakes in this language
  • Building count with a dict and forgetting to iterate keys in sorted order.
  • Not offsetting by mn for negative keys (negative indices wrap silently in Python and corrupt the histogram).
  • Using count[x - mn] += 1 before the write in the placement loop (off by one).
Language differences that matter here
  • Histogram storage: C++ std::vector<int> is contiguous and zeroed; JS/TS need .fill(0) (or Int32Array, which is zeroed and faster); Python [0] * k boxes each int.
  • Negative indices: Python wraps count[-1] to the last slot silently, C++ is undefined behaviour, JS creates a string property — always offset by mn.
  • Range overflow: mx - mn + 1 can overflow int in C++; JS doubles lose precision past 2^53; Python is unbounded.
  • Stability is identical in all four versions (left-to-right placement with exclusive prefix sums), which is what lets each serve as a radix-sort digit pass.

Complexity

Best
O(n + k)
Average
O(n + k)
Worst
O(n + k)
Space
O(n + k)

k = size of the key range. Stable (with left-to-right placement), not in-place, not comparison-based.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Integer keys with range k = O(n) — scores, ages, bytes, characters, enum codes.
  • As the stable digit-sort inside Radix Sort.
  • When you already need a histogram of the values.
  • Sorting a small range of colors/categories in a single pass (Dutch national flag alternative, with extra space).
Avoid it when
  • Keys spread over a huge range (k ≫ n, e.g. 64-bit integers or floats) — the count array is too big; use Radix Sort or a comparison sort.
  • Non-integer keys with no cheap integer mapping (strings of arbitrary length, objects under a custom comparator).
  • In-place sorting is required.

Alternatives

Radix SortBucket SortQuick SortMerge Sort

Common mistakes

  • Assuming keys start at 0 and indexing count[x] with negative or offset values — normalize by min.
  • Placing elements by iterating the input right to left with inclusive prefix sums but then also iterating left to right — mixing the two conventions breaks stability or overwrites slots.
  • Forgetting that stability only matters (and only holds) when elements carry satellite data.
  • Allocating count of size max instead of max - min + 1 for large minimums.

Interview patterns

  • Sort colors (0/1/2): count then overwrite; or Dutch national flag in place.
  • Group anagrams / valid anagram via 26-letter count arrays.
  • Top-k frequent elements with bucket-by-frequency (counting sort on counts).
  • H-index: count papers per citation count capped at n.
Interview questions on this
Mock interviews

Example problems

Group AnagramsmediumSort Colors (Dutch National Flag)mediumTop K Frequent ElementsmediumTask Schedulermedium