Counting sort — O(n + k), integer keys only

WHAT it is

Key vocabulary:

$n$ = number of elements to sort.
$k$ = the maximum key value (so the value range is $0 \dots k$ , a span of $k+1$ values).
Stable = equal keys keep their original relative order. This matters when we sort records by an integer field.

WHY it can beat $O(n \log n)$

The cost we pay: we need an array of size $k+1$ . If $k$ is huge (e.g. 64-bit keys), the algorithm becomes useless. Small $k$ is the whole deal.

HOW it works — derive it from scratch

We want a stable sort. Let's build the algorithm by reasoning about positions.

Step 1 — Count. Make an array count[0..k], all zeros. Scan the input once; for each element with key $v$ , do count[v] += 1. Now count[v] = how many times $v$ appears.

Why this step? To place value $v$ we must first know how many $v$ 's exist and how many values are below it.

Step 2 — Prefix sum (cumulative count). Replace count[v] with the running total $\sum_{i=0}^{v} \text{count}[i]$ . Now count[v] = the number of elements with key $\le v$ .

Why this step? If $m$ elements have key $\le v$ , then the last element with key $v$ must sit at output index $m-1$ (0-based). The prefix sum hands us exactly that boundary.

Step 3 — Place (scan input right-to-left). For each input element with key $v$ (going from last to first): $\text{output}[\,\text{count}[v]-1\,] = \text{element}; \qquad \text{count}[v] \mathrel{-}= 1.$

Why right-to-left? count[v]-1 gives the highest free slot for value $v$ . Filling from the back while scanning the input from the back means the last equal element lands in the last slot → original order is preserved → stable. Scanning forward would reverse equal keys.

Figure — Counting sort — O(n + k), integer keys only

The algorithm (pseudocode)

def counting_sort(A, k):          # keys in 0..k
    n = len(A)
    count = [0] * (k + 1)
    for x in A:                   # Step 1: tally
        count[key(x)] += 1
    for v in range(1, k + 1):     # Step 2: prefix sum
        count[v] += count[v - 1]
    out = [None] * n
    for x in reversed(A):         # Step 3: place, stably
        v = key(x)
        count[v] -= 1
        out[count[v]] = x
    return out

Worked examples

Common mistakes (steel-manned)

Flashcards

What assumption makes counting sort beat the

O(n\log n)

bound?

Keys are small integers in a known range

[0,k]

, used directly as array indices — no comparisons are made, so the comparison lower bound doesn't apply.

Time and space complexity of counting sort?

O(n+k)

time and

O(n+k)

space, where

n

=#elements,

k

=max key value.

What does count[v] represent after the prefix-sum step?

The number of elements with key

\le v

, i.e. the boundary index just past value

v

's block.

Why scan the input right-to-left during placement?

To keep the sort stable — the last equal element lands in the last slot, preserving original relative order.

Why size count as

k+1

not

k

Values range over

0..k

, which is

k+1

distinct values.

When does counting sort degrade badly?

When

k \gg n

(e.g.

k=O(n^2)

or 32-bit keys) — space and time blow up to

O(k)

How do you handle negative integer keys?

Offset every key by

-\min

so the range maps to

[0, \max-\min]

, then add

\min

back.

Why is stability of counting sort important in practice?

It lets counting sort serve as the stable per-digit pass inside radix sort.

Recall Feynman: explain it to a 12-year-old

Imagine sorting a big pile of exam papers by score, scores 0 to 10. Instead of comparing papers two at a time, you make 11 boxes labelled 0–10 and drop each paper in its box. Then you count: "I have 3 papers in box 0, 5 in box 1..." Once you know the counts, you know box 0's papers fill slots 1–3, box 1's fill slots 4–8, and so on — so you can lay them down in perfect order in one pass. You never compared two scores; you just used the score as an address. It's lightning fast because the scores are small whole numbers. If scores could be any giant number you'd need a billion boxes — useless.

Connections

Radix Sort — repeatedly applies stable counting sort, one digit at a time; that's why stability is non-negotiable.
Bucket Sort — a cousin that distributes into buckets, then sorts each; counting sort is the special case of one slot per value.
Prefix Sum / Cumulative Array — the engine that turns counts into positions.
Comparison Sort Lower Bound (Ω(n log n)) — the barrier counting sort sidesteps by not comparing.
Stability in Sorting — formal property exploited here.
Time Complexity / Big-O — for understanding when $O(n+k)$ actually wins.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, normal sorting algorithms (quicksort, mergesort) elements ko aapas mein compare karte hain — "ye chhota hai ya bada?" Isi compare karne ki wajah se unki limit $O(n\log n)$ hai. Counting sort ek alag chaal chalta hai: wo compare karta hi nahi! Agar tumhare keys chhote integers hain (jaise 0 se $k$ tak), to wo key ko hi array ka index bana leta hai. Matlab value 7 seedha box number 7 mein chali jaati hai — bina kisi comparison ke, $O(1)$ mein.

Process simple hai, teen C yaad rakho: Count, Cumulate, Cram. Pehle har value kitni baar aayi wo gin lo (count[v]). Phir prefix sum lo, taaki count[v] ka matlab ho jaaye "kitne elements $v$ se chhote ya barabar hain" — yahi humein batata hai ki har value ki output mein kahan jagah hai. Phir input ko ulta (right-to-left) ghoom kar har element ko uski sahi jagah par rakh do. Ulta isliye taaki stability bani rahe — yaani barabar keys ka original order na bigde.

Kyun important hai? Kyunki jab $k$ chhota ho (jaise marks 0–100, ya ek digit 0–9), counting sort linear time $O(n+k)$ mein kaam karta hai — comparison sorts se tez. Aur sabse badi baat: ye stable hai, isiliye radix sort iske upar bana hota hai, jahan har digit ko stable counting sort se sort karte hain.

Par ek warning: agar $k$ bahut bada hai (jaise 32-bit numbers, $k$ arbon mein), to itna bada count array banana padega ki memory aur time dono barbaad — tab counting sort bekaar hai. Toh rule yaad rakho: counting sort tabhi use karo jab keys chhote bounded integers hon.

Counting sort — O(n + k), integer keys only

WHAT it is

WHY it can beat $O(n \log n)$

HOW it works — derive it from scratch

The algorithm (pseudocode)

Worked examples

Common mistakes (steel-manned)

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Sorting & Searching

Connections