A non-comparison sorting algorithm that counts the occurrences of distinct key values to reconstruct a sorted array.
Overview
Beating the comparison lower bound
Every comparison-based sort needs Ω(n log n) comparisons in the worst case; that is a proven lower bound, not an engineering limit. Counting sort is faster because it never compares two elements. Instead it uses each value as an index, which is a fundamentally different source of information.
The requirement is that values are integers in a known, bounded range. If a value can index an array, counting sort applies.
Parameters
15
9
Visualization
Step: 0
1. Main Array
2. Frequency Count Array (Size: K + 1)
Click Step or Auto-Run to begin counting sort.
Algorithm Insight
Counting Sort is a Non-Comparison sorting algorithm, great when the range of inputs ($K$) is small compared to the array size ($N$).
1.Initialize a Count Array of size $K+1$ with zeros.
2.Iterate the main array. Increment Count[value] for each element read.
3.Iterate the Count Array. Overwrite the main array sequentially with valid elements.
Efficiency
Time ComplexityO(N + K)
Space ComplexityO(K)
Counting Sort: A Practical Guide
Sort without comparing anything. Tally how many times each value occurs, then rebuild the array from the tallies - linear time, provided the range of values is small.
The three passes
Sort [3, 1, 4, 1, 5, 3, 1] with values in 0–5.
1. Count. Walk the input, incrementing count[value]:
index: 0 1 2 3 4 5 count: 0 3 0 2 1 1
2. Prefix sum. Replace each entry with the running total, so each slot holds the number of elements less than or equal to that value:
count: 0 3 3 5 6 7
3. Place. Walk the input backwards, and for each element use count[value] − 1 as its output index, then decrement. The result is [1, 1, 1, 3, 3, 4, 5].
Three linear passes and no comparison anywhere.
The complexity, and the k that matters
Counting sort runs in O(n + k) time and O(n + k) space, where n is the number of elements and k is the size of the value range.
When k is O(n) this is linear and beats every comparison sort. When k is large it collapses: sorting 1,000 integers spread over the full 32-bit range means allocating a counting array of 4 billion entries to sort 1,000 values. The algorithm is not slow there so much as unusable.
So the honest rule is that counting sort is linear in n and k together, and it is only a good idea when k is comparable to n or smaller.
Sorting without comparing
Every comparison-based sort needs at least O(n log n) comparisons — that is a proven lower bound. Counting sort avoids it by not comparing at all.
Instead it counts how many times each value occurs, then reconstructs the array in order from the counts.
Sorting [4, 2, 2, 8, 3, 3, 1] with values in the range 0–8:
Step
Result
Count occurrences
[0,1,2,2,1,0,0,0,1] — index is the value
Read back in order
[1, 2, 2, 3, 3, 4, 8]
def counting_sort(arr, k):
"""k is the exclusive upper bound on values (0 <= x < k)."""
counts = [0] * k
for x in arr:
counts[x] += 1
out = []
for value, c in enumerate(counts):
out.extend([value] * c)
return out
That is O(n + k) time — one pass to count, one pass over the count array — and it beats O(n log n) whenever k is not much larger than n.
The catch: k
Counting sort's complexity contains the range of the values, not just their number.
n
Value range k
Counting sort
Comparison sort
1,000
0–100
Excellent
Slower
1,000
0–1,000,000
Terrible — a million-element array
Fine
1,000,000
0–255
Excellent
Slower
1,000
Arbitrary floats
Not applicable
The only option
So the requirements are strict:
Keys must be integers, or mappable to a small integer range. Floats and arbitrary strings do not qualify.
The range must be known in advance, or computed in an extra pass.
The range must be small relative to n. Sorting 100 values spread over 0 to a billion allocates a billion counters.
That last point is the practical filter. Counting sort is not a general-purpose sort; it is a specialised tool for bounded small-integer keys, and it is excellent there.
The stable version
The simple version above discards the original objects — it reconstructs values from counts, which is fine for plain integers and useless when each key has associated data.
The stable version computes cumulative counts to determine each element's output position, then places elements by walking the input backwards:
def counting_sort_stable(arr, key, k):
counts = [0] * k
for x in arr:
counts[key(x)] += 1
for i in range(1, k):
counts[i] += counts[i - 1] # cumulative: end position of each key
out = [None] * len(arr)
for x in reversed(arr): # backwards preserves stability
counts[key(x)] -= 1
out[counts[key(x)]] = x
return out
Two details are load-bearing. The cumulative counts give each key's ending position in the output. And iterating the input backwards is what makes it stable: the last occurrence of a key is placed last, preserving the original relative order.
That stability is not a nicety — it is what makes radix sort possible.
Exploration guide
Watch the tally build. Set Array Size to 20 and Max Value Limit (K) to 5, then press Next Step through the counting pass. No two input elements are ever compared — each one simply increments a bucket.
Make k small and see it win. Keep Array Size at 25 and set Max Value Limit (K) to 3. The counting array is tiny, buckets fill fast, and the whole sort finishes in three quick sweeps.
Make k large and watch the waste. Set Max Value Limit (K) to 15 with Array Size at 5. Now there are more buckets than elements and most sit empty — you are paying O(k) to sort n = 5. This is the failure mode, in miniature.
See stability in action. Press Randomize Array until duplicates appear, then Auto-Run. Equal values are emitted in their original relative order, because the placement pass walks the input backwards.
Why the last pass runs backwards
This is the detail that looks arbitrary and is not. Walking the input in reverse during the placement pass is what makes counting sort stable — equal elements keep their original relative order.
The prefix-sum array says where the last copy of each value belongs. Consuming the input from the back means the last equal element is placed at the highest available slot, the second-to-last just below it, and so on, preserving input order. Walking forwards places them in reverse.
Stability is not a nicety here: it is the entire reason radix sort works. Radix sort runs counting sort once per digit, from least significant to most, and relies on each pass preserving the order established by the previous one. Make counting sort unstable and radix sort produces garbage.
Common mistakes
Assuming values start at zero. With a range like 1000–1005, allocating 1006 buckets wastes almost all of them. Offset by the minimum: index with value − min and allocate max − min + 1.
Walking forwards in the placement pass. Silently destroys stability, and therefore silently breaks any radix sort built on top.
Using it on floats or strings. The value must be usable as an array index. Floats and arbitrary strings need a different approach — bucket sort or radix sort on their byte representation.
Ignoring k in the complexity. Calling counting sort “O(n)” without qualification is the most common mistake in exams and interviews. It is O(n + k), and k is what decides whether it is usable.
Key takeaway
Counting sort tallies occurrences, converts the tallies to positions with a prefix sum, and writes elements straight to their final slots — no comparisons, so the Ω(n log n) bound does not apply. It runs in O(n + k) and is only worth using when the value range k is comparable to n. Its stability, which comes from that backwards final pass, is what makes radix sort possible.
Radix sort: counting sort applied digit by digit
Counting sort fails on large ranges. Radix sort fixes that by sorting on one digit at a time, using counting sort for each pass.
Sorting 32-bit integers: instead of a range of 4 billion, do four passes over bytes, each with a range of 256.
O(d × (n + k)) where d = number of digits, k = base
For 32-bit integers in base 256: d = 4, k = 256, so O(4(n + 256)) — effectively linear.
The crucial requirement is that each pass must be stable, or earlier digits' ordering is destroyed. That is exactly why the stable version of counting sort matters, and why the two topics belong together.
Least significant digit first is the usual direction: sort by the last digit, then the next, and so on. After the final pass the array is fully sorted, because each pass preserves the previous ones' work.
Radix sort is genuinely used: for fixed-width integer keys at scale it outperforms comparison sorts, and it appears in database sorting, GPU sorting libraries and some string sorting.
Bucket sort, the third of the family
Bucket sort distributes elements into buckets by value range, sorts each bucket (often with insertion sort), and concatenates.
It works well when values are uniformly distributed: with n buckets and n elements uniformly spread, each bucket holds about one element and the total is O(n).
It degrades to O(n²) when the distribution is skewed and everything lands in one bucket — which is its main weakness, and why it is less robust than radix sort.
Sort
Requires
Complexity
Stable
Counting
Small integer range
O(n + k)
Yes, in the cumulative form
Radix
Fixed-width keys
O(d(n + k))
Yes, and must be
Bucket
Uniform distribution
O(n) average, O(n²) worst
Depends on the inner sort
Where these are used
Sorting by age, score, grade, priority — naturally small integer ranges.
Character and byte counting — the counts array is the histogram, and often the histogram is what you wanted.
Radix sort in databases and GPU libraries for large integer key sets.
Suffix array construction, which uses radix sort internally.
As a subroutine wherever keys are bounded integers and linear time matters.
Note the histogram point: computing the count array is frequently useful in itself, and the sorting is a bonus.
Where the k in O(n + k) starts to hurt
Counting sort beats the comparison lower bound by not comparing anything, and the price is a second term in the complexity that depends on the range of the values rather than how many there are. That term is easy to ignore until it is the whole cost, so it is worth watching it grow.
example_01.pyPython
def counting_sort(a, stats):
if not a:
return a
lo, hi = min(a), max(a)
k = hi - lo + 1
stats["k"] = k
counts = [0] * k
stats["ops"] += k # allocating the count array
for x in a:
counts[x - lo] += 1
stats["ops"] += 1 # pass 1: count
out, pos = [0] * len(a), 0
for i, c in enumerate(counts):
stats["ops"] += 1 # pass 2: walk every bucket
for _ in range(c):
out[pos] = i + lo
pos += 1
stats["ops"] += 1 # pass 3: write out
return out
import random
rng = random.Random(2)
n = 1000
print("n = %d in every row; only the RANGE of the values changes" % n)
print("%14s %10s %12s %14s" % ("value range", "k", "operations", "ops per item"))
for hi in (10, 100, 1000, 10 ** 4, 10 ** 6):
data = [rng.randrange(hi) for _ in range(n)]
st = {"ops": 0, "k": 0}
out = counting_sort(data, st)
assert out == sorted(data)
print("%14s %10d %12d %14.1f" % (
"0..%d" % hi, st["k"], st["ops"], st["ops"] / n))
# The first rows are the case counting sort is for: a thousand items with
# values under a thousand, sorted in a few operations each, no comparisons
# at all. The last row is the same thousand items with values up to a
# million -- and the cost per item is now in the thousands, because the
# algorithm walks a million empty buckets to find them.
#
# The rule that falls out: counting sort is O(n + k), and it is a good
# idea only while k is comparable to n. Sorting a thousand 32-bit integers
# by this method would allocate four billion counters.
#
# Comparison sorts do not care about the range at all:
import math
print()
print("a comparison sort would need about n log2 n = %.0f comparisons," % (
n * math.log2(n)))
print("for any of the rows above.")
# The other property worth having is stability, and the naive version
# above threw it away -- it rebuilt the values from the counts rather than
# moving the original records. With records that carry a payload you need
# the prefix-sum version, which places each item by looking up where its
# bucket ends and walking the input BACKWARDS.
records = [("Ada", 2), ("Bala", 1), ("Chen", 2), ("Dara", 1), ("Eze", 0)]
def stable_counting(recs):
k = max(r[1] for r in recs) + 1
counts = [0] * k
for _, key in recs:
counts[key] += 1
for i in range(1, k):
counts[i] += counts[i - 1] # prefix sums: end position of each bucket
out = [None] * len(recs)
for rec in reversed(recs): # backwards is what makes it stable
counts[rec[1]] -= 1
out[counts[rec[1]]] = rec
return out
print()
print("input: ", [r[0] for r in records])
print("sorted:", [r[0] for r in stable_counting(records)])
# Ada and Chen both have key 2 and come out in that order; Bala and Dara
# both have key 1 and come out in that order. Walk the input forwards
# instead and every group comes out reversed -- which is the bug that
# breaks radix sort, since radix sort is counting sort applied repeatedly
# and depends on each pass preserving the last one's work.
Output
Questions people ask
Why is counting sort not O(n log n)-bound? The lower bound applies to comparison-based sorts. Counting sort never compares two elements.
When is it worth using? When keys are integers in a range comparable to n. If k is much larger than n, it is worse than sorting normally.
Can it handle negative numbers? Yes — offset by the minimum value, or index the count array from the minimum.
Can it sort floats or strings? Not directly. Radix sort handles fixed-width strings; floats need bit-level tricks or a different sort.
Is it stable? The cumulative-count version is, and it must be for radix sort to work.
What does Python use? Timsort, a comparison sort, because it must handle arbitrary comparable objects. Counting sort is something you write for a specific bounded-key case.
Recap in one screen
Count occurrences and read back in order: O(n + k), with no comparisons at all.
k is the value range, so it only wins when the range is comparable to the number of elements.
The cumulative-count version is stable and preserves associated data, which the naive version discards.
Radix sort applies stable counting sort digit by digit, making large integer ranges linear.
Bucket sort is the distribution-dependent cousin: O(n) when values are uniform, O(n²) when skewed.
Run it in Python
No comparison between two elements appears anywhere in this program. It sorts by counting, which is how it beats the O(n log n) bound — and the last block shows what that costs when the value range is large.
counting_sort.pyPython 3
# Counting sort: count how many of each value there are, then rebuild.
# Not a comparison sort - it never asks "is x < y?" at all.
def counting_sort(a):
if not a:
return []
lo, hi = min(a), max(a)
k = hi - lo + 1
print(f"n = {len(a)}, value range k = {k} ({lo}..{hi})")
counts = [0] * k
for value in a:
counts[value - lo] += 1
# Only worth printing while it fits on a line - see the second example.
print("counts :", counts if k <= 20 else f"<{k} counters, {len(a)} non-zero>")
# Running total: counts[i] becomes "how many items are <= i".
for i in range(1, k):
counts[i] += counts[i - 1]
print("prefix :", counts if k <= 20 else f"<{k} counters, summed in order>")
out = [None] * len(a)
for value in reversed(a): # reversed keeps the sort stable
counts[value - lo] -= 1
out[counts[value - lo]] = value
return out
data = [4, 2, 2, 8, 3, 3, 1]
print("start :", data)
print("sorted:", counting_sort(data))
print()
print("Now the same algorithm on a wide range:")
wide = [5, 100_000, 3]
print("start :", wide)
print("sorted:", counting_sort(wide))
print()
print("Three items, a hundred thousand counters, and a pass over every one of")
print("them. O(n + k) is only a win when k behaves.")
Output
How the code works
counts[value - lo] += 1The value itself is the index. That is the trick, and it is also the restriction: this only works for keys that can be used as array offsets.
for i in range(1, k): counts[i] += counts[i - 1]Turns counts into positions. After this, counts[v] is the number of items less than or equal to v — which is exactly where the last v belongs in the output.
for value in reversed(a):Walking backwards, combined with decrementing before writing, keeps equal items in their original order. Iterate forwards and the sort still works but is no longer stable — which would break radix sort, its main customer.
out[counts[value - lo]] = valueEach item is placed directly at its final index. No item is ever compared with another, so the O(n log n) lower bound for comparison sorts simply does not apply.
k = hi - lo + 1The whole cost story. O(n + k) is linear when k is comparable to n, and a disaster when it is not — as the three-item example shows.
Change one thing
Sort exam marks: [random.randint(0, 100) for _ in range(50)]. Fifty items, 101 counters — this is the shape counting sort is for.
Iterate forwards instead of reversed(a), and sort (value, tag) pairs by value. Watch the tags come out in the wrong order.
Remove the - lo offset and sort a list with negative numbers. The IndexError is why the offset is there.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
How does counting sort beat the O(n log n) lower bound?
The bound applies to comparison sorts. Counting sort uses the value as an array index, so the proof simply does not cover it.
Why does the final loop iterate over reversed(a)?
Walking backwards while decrementing before writing keeps equal items in their original order. Radix sort depends on that, so getting it wrong breaks the algorithm built on top.
The program sorts [5, 100000, 3]. What is the problem?
O(n + k) is linear only when k is comparable to n. Three items and a hundred thousand counters is the case that makes the cost obvious.
Cheat sheet
Counting Sort
Every comparison-based sort needs Ω(n log n) comparisons in the worst case; that is a proven lower bound, not an engineering limit. Counting sort is faster because it never compares two elements. Instead it uses each value as an index, which is a fundamentally different source of information.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.