Counting Sort — Algorithm Visualized
Learn counting sort — frequency array, O(n + k) integer sorting, scatter and gather phases, interactive visualizer, and when to use over comparison sorts.
Introduction
Counting sort counts how many times each integer value appears, then outputs values in order — no comparisons, O(n + k) when k is the value range.
Quick index
| # | Section |
|---|---|
| 1 | How it works |
| 2 | Interactive visualizer |
| 3 | Full implementation |
| 4 | Complexity analysis |
| 5 | Real-life examples |
1. How it works
Unsorted → count[value]++ for each element → gather 0..k in order2. Interactive visualizer
Counting Sort — Step Visualizer
Count occurrences of each integer in range 0..k, then gather in order.
Unsorted
Step 1 — Input array
const arr = [4, 2, 2, 8, 3, 3, 1] // integers in range 0..k
Counting sort counts occurrences of each value — no comparisons.
Time
O(n + k)
Space
O(n + k)
Stable
Yes*
3. Full implementation
function countingSort(arr, maxVal) {
const count = Array(maxVal + 1).fill(0)
for (const num of arr) count[num]++
const sorted = []
for (let v = 0; v <= maxVal; v++) {
while (count[v]-- > 0) sorted.push(v)
}
return sorted
}Function calls with output
// ── Demo calls — output shown on the right ──
const arr = [4, 2, 2, 8, 3, 3, 1]
countingSort(arr, 8) // → [1, 2, 2, 3, 3, 4, 8]
countingSort([5, 5, 5], 5) // → [5, 5, 5]4. Complexity analysis
| Metric | Value |
|---|---|
| Time | O(n + k) |
| Space | O(n + k) |
| Stable | Yes (with prefix-sum variant) |
5. Real-life examples
| Scenario | Why counting sort |
|---|---|
| Exam grade distribution | Scores 0–100 — k=101, n=10,000 students → O(n+k) beats O(n log n) |
| Vote counting | Count ballots per candidate ID (small integer range) |
| Age demographics histogram | Ages 0–120 — one bucket per year |
| Character frequency in text | ASCII 0–127 — count letters for compression/huffman |
| Inventory by star rating | 1–5 stars — count reviews per rating tier |
Exam grade histogram
Scores 0–100 — counting sort is O(n + k) where k=101 buckets.
Index → value
6 student scores — duplicates allowed, range 0–100.
Real-world implementation
function countingSort(arr, maxVal) {
const count = Array(maxVal + 1).fill(0)
for (const v of arr) count[v]++
const out = []
for (let i = 0; i <= maxVal; i++) {
while (count[i]-- > 0) out.push(i)
}
return out
}
function gradeHistogram(arr, maxVal = 100) {
const freq = Array(maxVal + 1).fill(0)
for (const s of arr) freq[s]++
return freq
}Full working code for the scenario above.
Function calls with output
// ── Function calls with output ── const scores = [87, 92, 65, 87, 100, 73]
Side output shows return value after each call — step through to trace execution.
Summary
Counting sort beats O(n log n) when k = O(n) — exam scores, ages, small enums.
Next reads: Radix Sort · Merge Sort
Subscribe to my newsletter
Stay up to date and get notified when I share new contents.
No spam ever, unsubscribe anytime