Radix sort — LSD, MSD; O(d(n+k)) — Hinglish notes

3.6.7 · Coding › Sorting & Searching

Radix Sort KYA hai?

Key vocabulary:

$n$ = elements ki sankhya.
$k$ = radix / possible digit values ki sankhya (e.g. decimal ke liye $k = 10$ , bytes ke liye $k = 256$ ).
$d$ = digit positions ki sankhya = $⌈ lo g_{k} (max key)⌉$ .

LSD radix sort KYU kaam karta hai? (Scratch se Derivation)

Humhe ek invariant chahiye. Claim:

Digit positions $0, 1, \dots, i$ (least significant pehle) process karne ke baad, array un $i + 1$ low digits se bane number ke hisaab se sorted hai.

Induction se Proof.

Base case ( $i = 0$ ): hum stably digit 0 se sort karte hain. Array sabse low digit ke hisaab se sorted hai. ✓

Inductive step: Maano pass $i$ ke baad array digits $0.. i$ se sorted hai. Pass $i + 1$ mein hum stably digit $i + 1$ se sort karte hain.

Different digit $i + 1$ wale do keys sahi relative order mein aate hain, kyunki bada digit value ko dominate karta hai.
Same digit $i + 1$ wale do keys apna pehle wala relative order rakhte hain — kyunki sort stable hai — aur woh pehle wala order digits $0.. i$ pe already sahi tha. ✓

Toh saare $d$ passes ke baad array fully sorted hai. ∎

KAISE: algorithm (LSD with counting sort per digit)

def lsd_radix(a, k=10):
    if not a: return a
    maxv = max(a)
    exp = 1                       # 1, k, k^2, ...  selects the digit
    while maxv // exp > 0:        # loop runs d times
        a = counting_sort_by_digit(a, exp, k)
        exp *= k
    return a

def counting_sort_by_digit(a, exp, k):
    n = len(a)
    out = [0]*n
    count = [0]*k
    for x in a:                       # 1) tally this digit
        count[(x // exp) % k] += 1
    for i in range(1, k):             # 2) prefix sums -> end positions
        count[i] += count[i-1]
    for x in reversed(a):             # 3) place RIGHT-to-LEFT => STABLE
        d = (x // exp) % k
        count[d] -= 1
        out[count[d]] = x
    return out

Running time $O (d (n + k))$ KYU hai (Derivation)

Ek counting-sort pass ka cost:

tally loop: $O (n)$
prefix-sum loop: $O (k)$
placement loop: $O (n)$

Toh ek pass $= O (n + k)$ . Hum exactly $d$ passes karte hain.

$T (n) = d \cdot O (n + k) = O (d (n + k))$

Yeh $O (n lo g n)$ ko kab beat karta hai? Agar keys bounded hain toh $d$ constant hai (e.g. 32-bit ints $k = 2^{8}$ ke saath ⇒ $d = 4$ ) aur $k = O (n)$ , toh $T = O (n)$ — linear.

MSD vs LSD

	LSD	MSD
Direction	right → left	left → right
Structure	flat loop, $d$ passes	recursive, buckets mein divide
Hamesha saare $d$ digits examine karta hai?	Haan	Nahi — distinguishing prefix pe jaldi rok sakta hai
Stable?	Haan	Haan (agar buckets stable rakhe jaayein)
Best for	fixed-width ints	variable-length keys / strings, partial sort
Har pass mein poore array ko touch karta hai	Haan	Sirf relevant bucket ko

Figure — Radix sort — LSD, MSD; O(d(n+k))

Worked Example 1 — LSD on $[170, 45, 75, 90, 802, 24, 2, 66]$ , base 10

Pass exp=1 (units digit): digits → 0,5,5,0,2,4,2,6. Stable counting sort deta hai [170, 90, 802, 2, 24, 45, 75, 66]. Yeh step kyun? Hum pehle least significant digit se sort karte hain taki baad ke passes (jo dominate karte hain) ties ke beech is order ko preserve karne ke liye stability pe rely kar sakein.

Pass exp=10 (tens digit): digits → 7,9,0,0,2,4,7,6 → [802, 2, 24, 45, 66, 170, 75, 90]. Yeh step kyun? Equal tens digit wale keys (170 & 75 dono ka tens 7 hai) mein pehle wala unit order stability se preserve hota hai.

Pass exp=100 (hundreds digit): digits → 8,0,0,0,0,1,0,0 → [2, 24, 45, 66, 75, 90, 170, 802]. ✅ Sorted. Yeh step kyun? Max value 802 ke 3 digits hain, toh $d = 3$ passes kaafi hain; top digit ke baad array fully ordered hai.

Worked Example 2 — MSD on strings `["bat","apple","ant","bad"]`

char 0 se sort karo: bucket a = {apple, ant}, bucket b = {bat, bad}. Yeh step kyun? Most significant character data ko split karta hai; buckets independent hain.

Bucket a mein char 1 pe recurse karo: dono ke n/p hain... actually "apple"[1]=p, "ant"[1]=n → ant pehle apple se. Bucket a = [ant, apple]. Yeh step kyun? Sirf yeh do elements touch hote hain — MSD kaam ko localize karta hai.

Bucket b mein char 1 pe recurse karo: "bat"[1]=a, "bad"[1]=a (tie) → char 2 pe recurse karo: d < t → [bad, bat]. Yeh step kyun? Hum sirf utna hi neeche jaate hain jitna ties todhne ke liye zaroori ho.

Concatenate karo: [ant, apple, bad, bat]. ✅

Worked Example 3 — 32-bit ints ke liye radix choose karna

Keys up to $2^{32} - 1$ tak. $k = 2^{8} = 256$ choose karo (ek byte per pass sort karo). $d = 32/8 = 4$ passes. Cost $= 4 (n + 256) = O (n)$ bade $n$ ke liye. Yeh step kyun? Bada $k$ → kam passes ( $d = ⌈ 32/ lo g_{2} k ⌉$ ) lekin bada count array. $k = 256$ dono ko balance karta hai; count array (256 ints) $n$ ke mukable negligible hai.

Active Recall

Recall Feynman — ek 12-saal ke bachche ko explain karo

Socho ek 3-digit number wale player cards ki stack sort kar rahe ho. Tum 10 trays banate ho 0–9 label karke. Pehle tum har card ko uski last digit se match karti tray mein daalte ho, phir trays ko 0→9 order mein wapas uthao (ek tray ke andar cards usi order mein raho). Middle digit use karke repeat karo, phir pehle digit se. Teen rounds ke baad cards magically order mein hain — aur tumne kabhi directly do cards compare nahi kiye! Trick: ties ko usi order mein rakhna jisme woh already the (wahi "stable" hai), aur pehle ke rounds quietly sorted rehte hain.

Flashcards

Radix sort core idea

Keys ko digit-by-digit stable bucket (counting) sort use karke sort karo per digit, koi whole-key comparisons nahi.

Per-digit sort stable kyun hona chahiye

Taaki current digit pe equal elements ka woh order rahe jo pehle ke (lower) digits ne establish kiya tha, inductive invariant preserve karte hue.

LSD processing direction

Least significant digit pehle, rightmost → leftmost;

d

passes ka flat loop.

MSD processing direction

Most significant digit pehle, leftmost → har bucket mein recurse karo.

Radix sort ki time complexity

O (d (n + k))

jahan

d

=digits ki sankhya,

n

=elements,

k

=radix.

Space complexity

O (n + k)

output aur count arrays ke liye.

d ka formula

d = ⌈ lo g_{k} (max key)⌉

Ek counting-sort pass ka cost

O (n + k)

: tally

O (n)

+ prefix sum

O (k)

+ placement

O (n)

Radix sort true O(n) mein kab run karta hai

Jab

d

constant ho aur

k = O (n)

, yani keys

n

ke relative chhoti hon.

Radix quicksort se bura kyun ho sakta hai

Agar keys bahut badi hain,

d = lo g_{k} (max) = Θ (lo g n)

, jo

Θ (n lo g n)

plus bade constants/memory deta hai.

LSD vs MSD: kaun saare digits padhta hai

LSD hamesha saare

d

digits padhta hai; MSD distinguishing prefix pe jaldi rok sakta hai.

MSD ka best use

Variable-length keys / strings, ya partial sorting jahan chhote prefixes keys ko alag karein.

Counting sort mein elements right-to-left kyun place karte hain

Input ko reverse mein walk karna prefix-sum end indices ke saath stable placement deta hai.

Connections

Counting Sort — har radix pass ke andar ka stable engine.
Comparison Sort Lower Bound — $Ω (n lo g n)$ ki wall jise radix sidestep karta hai.
Stability in Sorting — woh property jis par correctness proof rely karti hai.
Bucket Sort — cousin jo digit ke bajaye value range se distribute karta hai.
Big-O Notation — $O (d (n + k))$ aur chhupe hue $lo g$ ko interpret karna.
Tries — MSD radix sort essentially level by level ek trie build karna hai.