Problem Statement
Counting Sort
Imagine you have a bag of numbered tokens, and every token holds a small number, say from 1 to 8. To sort them, you do not compare tokens against each other. Instead you set up a row of buckets, one bucket for each possible number, and you toss each token into its matching bucket. When you are done, you walk down the row of buckets in order and pour them out. That gives you a sorted pile. That is Counting Sort. The word "non-comparison-based" just means it never asks "is this token bigger than that one?", it only counts how many of each value it saw. This makes it very fast when the values fall in a small, known range. Most sorting methods that compare items cannot go faster than O(n log n) (a math way of saying the work grows a bit faster than the number of items). Counting Sort sidesteps that limit and runs in O(n + k) time, where n is how many numbers you have and k is the size of the value range. It is often used as a helper step inside Radix Sort, and it works best for whole numbers in a limited range.
Signals to notice
Brute force first
Comparison sort. Doesn't exploit the bounded range. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.
The key insight
Count occurrences of each value in a counting array, then reconstruct the sorted output from counts. where k is the range of values. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.
Trace it on arr=[4, 2, 2, 8, 3, 3, 1]
min=1, max=8 -> count = [0,0,0,0,0,0,0,0] (8 slots, index i maps to value i+1) Tally pass over arr: count[num-1]++ for each -> count = [1,2,2,1,0,0,0,1] (one 1, two 2s, two 3s, one 4, one 8) Rebuild i=0 (val 1): count[0]=1 -> write 1; arr=[1], idx=1 i=1 (val 2): count[1]=2 -> write 2,2; arr=[1,2,2], idx=3 i=2 (val 3): count[2]=2 -> write 3,3; arr=[1,2,2,3,3], idx=5 i=3 (val 4): count[3]=1 -> write 4; arr=[1,2,2,3,3,4], idx=6 i=4..6 (vals 5,6,7): counts all 0 -> skip; i=7 (val 8): count[7]=1 -> write 8; arr=[1,2,2,3,3,4,8], idx=7 Return arr = [1, 2, 2, 3, 3, 4, 8]
What must stay true
If you know every value in [0, k], a count array of size k+1 tells you exactly how many of each value exist. Reconstructing the sorted array from counts is linear. If that remains true after every update, the rest of the reasoning has a stable place to stand.
Shape of the loop
min, max = min(arr), max(arr) count = array of zeros, size (max - min + 1) for num in arr: count[num - min] += 1 idx = 0 for i in 0..len(count): while count[i] > 0: arr[idx++] = i + min; count[i] -= 1 return arr
Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Not stable by default — for stability, compute prefix sums of counts and place elements in reverse order of the original array. The fix is usually to return to the meaning of each move, not just the steps themselves.