Non-Comparison Sort | Integer Keys | O(n+k) Time
Picture a teacher with a tall stack of graded exams, every score a whole number from 0 to 100. Most sorting methods compare two papers at a time. Counting sort refuses to compare anything at all. Instead it lays out a labelled tray for every possible score, drops each exam into the tray that matches its score, then sweeps the trays from low to high and stacks the papers back up. They come out in order, and no two papers were ever held side by side.
That tallying is the whole trick. Call the list length $n$, and let every value sit in the range $0$ to $k$. First build a count array $C$: walk the input once and, for each value $v$, do $C[v]\,{+}{+}$. For the list $[3,1,4,1,5]$ you finish with $C[1]=2$, $C[3]=1$, $C[4]=1$, $C[5]=1$ — a histogram of the data. One pass, $n$ steps.
Now turn those counts into positions. Replace each entry with a running total, $C[v]\mathrel{+}=C[v-1]$, so that $C[v]$ becomes the number of elements less than or equal to $v$ — which is exactly the slot where the last $v$ belongs. Then walk the input backward: for each value $A[i]$, place it at $B[\,C[A[i]]-1\,]$ and decrement $C[A[i]]$. Going backward keeps equal keys in their original order, which makes counting sort stable — the property that lets Radix Sort chain it digit by digit.
Add the passes and the cost is $O(n) + O(k) + O(n) = O(n+k)$. When the range is modest, $k = O(n)$, that is plain linear time — faster than the $\Omega(n\log n)$ floor that traps every comparison sort. The catch is memory: the trays need $O(k)$ space, so a huge value range ruins it. The sliders above set exactly these two knobs — Array Size is $n$, Max Value is $k$.
Try this in the sim above. Pick the Small k (0–3) preset and watch just a handful of trays do all the work — the count array stays tiny while the output fills cleanly. Switch to Many Duplicates and notice one count bar tower over the rest, yet the running time barely changes. Finally, step through the placement phase slowly and watch the cursor move right to left: that backward sweep is stability happening in front of you.
| Symbol | Meaning |
|---|---|
| n | Number of input elements |
| k | Range of values [0..k] |
| C[0..k] | Count/prefix-sum array |
| B[0..n-1] | Output array |
❌ "Counting Sort is always O(n), ignoring k."
✅ Time is O(n+k). If k = n², Counting Sort is O(n²), worse than comparison sorts. The k=O(n) condition is critical.
❌ "The count array directly gives sorted output."
✅ Count array only tells how many times each value appears. The prefix sum and backward placement phases are needed for the actual sorted array, especially for stability.
❌ "Counting Sort works on floating-point numbers."
✅ Counting Sort requires integer keys to use as array indices. Floats cannot be used as indices without conversion (which changes the algorithm fundamentally).
❌ Initializing C[] with size n instead of k+1.
✅ C[] must have size k+1 (one slot for each possible value 0 through k). Using n causes index-out-of-bounds when A[i] > n−1.
❌ Running placement loop forward (i=0 to n−1) when stability is needed.
✅ Stable placement requires backward traversal (i=n−1 downto 0). Forward traversal produces a sorted output but is unstable — equal elements' relative order is reversed.
❌ Forgetting to decrement C[A[i]] after placement.
✅ C[A[i]]-- is essential. Without it, all duplicates would be placed at the same position, overwriting each other.