Counting Sort: How to Sort in O(n + k) Without a Single Comparison
Counting sort tallies how many times each value appears, then rebuilds the array from those counts — an O(n + k) sort with no comparisons, explained step by step.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Every sort you learned first — merge, quick, heap — plays the same game: pick two elements, compare them, decide who goes left. That game has a hard floor. Any sort built purely on comparisons cannot beat O(n log n), no matter how clever the pivoting gets.
Counting sort refuses to play. It never asks "is a bigger than b?" even once. Instead it asks a different question — how many times does each value appear? — and reconstructs the answer from a tally. When your values are integers packed into a small range, that shortcut turns sorting into a linear-time scan.
The problem
Given an array of non-negative integers, return the same values in ascending order. The catch that makes counting sort possible: the values are integers, and their range (largest minus smallest) is not enormous.
Input: arr = [4, 2, 2, 8, 3, 3, 1]
Output: [1, 2, 2, 3, 3, 4, 8]Notice the two 2s and two 3s survive into the output as duplicates. Counting sort handles repeats for free — they're just a higher tally in the same bucket. The only requirement is that each value can serve as an index into an array, which is why plain integers are the natural fit.
The brute force baseline
The comparison-based approach everyone reaches for is a nested-loop sort, or a library sort under the hood:
function sortByComparison(arr) {
return [...arr].sort((a, b) => a - b);
}Array.prototype.sort is a fine, general-purpose tool — it works on strings, objects, anything with an ordering. But generality has a price. A comparison sort must, in the worst case, perform on the order of n log n comparisons because it's discovering the ordering one pairwise question at a time. For n = 10⁶ that's roughly 20 million comparisons. If your data is nothing but small integers, you're paying for a flexibility you never use.
The key insight: index by value, not by rank
Here's the reframe. A comparison sort figures out each element's rank — its position relative to the others — by interrogating pairs. Counting sort skips rank entirely and uses the value itself as an address.
If you know that the value 3 appears twice and the value 4 appears once, you don't need to compare anything to place them. You know 3s come before 4s because 3 < 4 is a fact of arithmetic, not something to discover. So:
- Walk the input once and tally occurrences into a
countarray wherecount[v]= how many times valuevshowed up. - Walk the
countarray left to right — from smallest value to largest — and emit each value as many times as its tally.
Because you visit the count buckets in ascending index order, the output comes out sorted. This is the non-comparison sort pattern: replace the comparison with direct addressing into a frequency table.
The optimal solution
This is exactly the algorithm the visualizer steps through, line for line:
function countingSort(arr) {
let max = Math.max(...arr);
let count = new Array(max + 1).fill(0);
for (let x of arr) {
count[x]++;
}
let index = 0;
for (let i = 0; i < count.length; i++) {
while (count[i] > 0) {
arr[index] = i;
index++;
count[i]--;
}
}
return arr;
}Three moves, no comparisons:
- Size the tally.
max + 1buckets so every value from0tomaxhas a home. The+ 1matters — a max of8needs indices0through8, which is nine slots. - Count. One pass over the input increments
count[x]for each value. After this loop,countholds the full frequency histogram. - Reconstruct. For each bucket
iin ascending order, write the valueiback intoarrexactlycount[i]times, decrementing the tally as you go. Theindexpointer tracks where the next value lands.
Walkthrough
Trace arr = [2, 5, 2, 1]. Max is 5, so count has six buckets, indices 0–5.
Counting phase — one pass over the input:
| Read | Value | count after |
|---|---|---|
| 1 | 2 | [0, 0, 1, 0, 0, 0] |
| 2 | 5 | [0, 0, 1, 0, 0, 1] |
| 3 | 2 | [0, 0, 2, 0, 0, 1] |
| 4 | 1 | [0, 1, 2, 0, 0, 1] |
The histogram now reads: one 1, two 2s, one 5. Everything else is zero.
Reconstruction phase — walk count left to right, emit each value count[i] times:
| i | count[i] | Action | index | arr so far |
|---|---|---|---|---|
| 0 | 0 | skip (empty bucket) | 0 | [] |
| 1 | 1 | write 1, then count[1]→0 | 1 | [1] |
| 2 | 2 | write 2, write 2, count[2]→0 | 3 | [1, 2, 2] |
| 3 | 0 | skip | 3 | [1, 2, 2] |
| 4 | 0 | skip | 3 | [1, 2, 2] |
| 5 | 1 | write 5, count[5]→0 | 4 | [1, 2, 2, 5] |
Final result: [1, 2, 2, 5]. Not one comparison was made — the ascending order fell out of visiting buckets in index order, and the duplicate 2 appeared naturally because its bucket held a count of two.
Complexity
Let n = number of elements and k = the value range (max + 1).
| Metric | Big-O | Why |
|---|---|---|
| Time | O(n + k) | One pass to count (n), one pass over buckets to emit (k); the inner while emits exactly n values total |
| Space | O(k) | The count array holds one slot per possible value |
| Comparison-sort baseline | O(n log n) time | Pairwise comparisons discover ordering one question at a time |
The reconstruction's nested while looks like it could be O(n·k), but it isn't: across all buckets the while body runs exactly n times total, because every element gets placed once. So the two phases add up to O(n + k), not multiply. Counting sort wins big when k is on the order of n or smaller, and loses badly when k dwarfs n — sorting [0, 1000000] would allocate a million-slot array for two values.
Common mistakes
- Off-by-one on the count size. Allocating
new Array(max)instead ofmax + 1drops the largest value into an out-of-bounds slot. The maximum value needs its own index. - Assuming it handles negatives. Values are used directly as array indices, so a negative number throws or silently corrupts. To support negatives, offset every value by
-minand shift back when reconstructing. - Reaching for it when the range is huge. With values up to a billion,
countis a billion-element array — memory blows up long before it's faster than a comparison sort. Counting sort is for dense, bounded integer ranges. - Expecting stability from this version. The reconstruct-from-counts variant above discards the original elements and rebuilds pure values, so for plain integers "stability" is meaningless. But if you're sorting records by an integer key and must preserve input order among equal keys, you need the prefix-sum variant, not this one.
Where this pattern shows up next
Counting sort is the foundation for a whole family of non-comparison and hybrid sorts:
- Radix Sort — runs a stable counting sort digit by digit to sort large integers whose full range is too big for a single count array.
- Counting Sort - Stable - Logic — why placing elements right-to-left with prefix-sum end-pointers preserves the order of equal keys.
- Counting Sort - Stable - Code — the line-by-line implementation of that stable version, the one radix sort depends on.
- Quick Sort — the comparison-based counterpart, and a reminder of the O(n log n) floor counting sort sidesteps.
Watch the count array fill and the buckets drain into sorted order in the Counting Sort visualizer.
FAQ
Why is counting sort faster than O(n log n)?
Because it never compares two elements. The O(n log n) lower bound only applies to sorts that determine ordering through pairwise comparisons — each comparison yields one bit of information, and you need log(n!) ≈ n log n of them to distinguish all possible orderings. Counting sort gets its ordering from arithmetic instead: value 3 precedes value 4 because 3 < 4 is a known fact, not a question to ask. That lets it run in O(n + k), which is linear when the value range k is comparable to n.
When should I not use counting sort?
When the range of values is large relative to the number of elements. Counting sort allocates a bucket for every possible value from 0 to max, so sorting a handful of values spread across a huge range wastes enormous memory and time on empty buckets. It's also unsuitable for floating-point numbers, arbitrary strings, or anything you can't cheaply map to a bounded integer index. For general-purpose sorting with unknown or wide-ranging data, a comparison sort like quicksort or mergesort is the right default.
Is counting sort stable?
The value-reconstruction version shown here is not stable in a meaningful sense — it rebuilds the output from raw counts and discards the original elements, so there's nothing left to preserve order between. When people say "counting sort is stable," they mean the prefix-sum variant that computes cumulative counts, then places original elements from right to left into their final positions. That version keeps equal-keyed records in their input order, which is exactly why radix sort relies on it.
How does counting sort handle duplicate values?
Duplicates require zero special handling. Each occurrence simply increments the same bucket, so count[v] ends up holding the total number of times v appeared. During reconstruction, the inner while loop emits value v exactly that many times before moving on. In the walkthrough, the two 2s both landed in count[2], which reached a tally of 2, and both were written back into the output — no branching, no edge case.
Can counting sort work with negative numbers?
Not directly, because it uses each value as an array index and negative indices aren't valid. The standard fix is to shift the whole range: find the minimum value, subtract it from every element so the smallest becomes 0, run counting sort on the shifted values, then add the minimum back when reconstructing. This costs one extra pass to find the min and keeps the algorithm O(n + k), where k is now max - min + 1.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.