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

3.6.6 · Coding › Sorting & Searching

YEH HAI KYA

Key vocabulary:

• $n$ = sort kiye jaane wale elements ki sankhya.
• $k$ = maximum key value (toh value range hai $0\dots k$, jo $k+1$ values ka span hai).
• Stable = equal keys apna original relative order maintain karte hain. Yeh tab matter karta hai jab hum records ko kisi integer field se sort karte hain.

KYUN yeh $O(n\log n)$ ko beat kar sakta hai

Jo cost hum pay karte hain: humhe size $k+1$ ka array chahiye. Agar $k$ bahut bada ho (jaise 64-bit keys), toh algorithm useless ho jaata hai. Chhota $k$ hi poori baat hai.

KAISE kaam karta hai — scratch se derive karo

Hum ek stable sort chahte hain. Positions ke baare mein reason karke algorithm build karte hain.

Step 1 — Count karo. Array count[0..k] banao, sab zeros. Input ek baar scan karo; key $v$ wale har element ke liye count[v] += 1 karo. Ab count[v] = $v$ kitni baar appear hota hai.

Yeh step kyun? Value $v$ ko place karne ke liye pehle jaanna zaroori hai ki kitne $v$'s hain aur kitne values usse neeche hain.

Step 2 — Prefix sum (cumulative count). count[v] ko running total ${\sum }_{i=0}^v\text{count}[i]$ se replace karo. Ab count[v] = key $\le v$ wale elements ki sankhya.

Yeh step kyun? Agar $m$ elements ki key $\le v$ hai, toh key $v$ wala aakhri element output index $m-1$ (0-based) par hoga. Prefix sum exactly wahi boundary deta hai.

Step 3 — Place karo (input right-to-left scan karo). Har input element ke liye key $v$ ke saath (last se first ki taraf): $\text{output}[\text{count}[v]-1]=\text{element};\text{count}[v]-=1.$

Right-to-left kyun? count[v]-1 value $v$ ke liye sabse upar wala free slot deta hai. Peeche se fill karte hue aur input ko peeche se scan karte hue, aakhri equal element aakhri slot mein jaata hai → original order preserve hoti hai → stable. Forward scan karna equal keys ko reverse kar deta.

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

Connections

• Radix Sort — baar baar stable counting sort apply karta hai, ek digit at a time; isliye stability non-negotiable hai.
• Bucket Sort — ek cousin jo buckets mein distribute karta hai, phir har bucket sort karta hai; counting sort iska special case hai jab har value ke liye ek slot ho.
• Prefix Sum / Cumulative Array — woh engine jo counts ko positions mein convert karta hai.
• Comparison Sort Lower Bound (Ω(n log n)) — woh barrier jise counting sort sidestep karta hai compare na karke.
• Stability in Sorting — formal property jo yahan exploit ki gayi hai.
• Time Complexity / Big-O — samajhne ke liye ki $O(n+k)$ actually kab jeetta hai.

Concept Map