Merge sort — divide and conquer, O(n log n), stable, proof of correctness

3.6.2 · Coding › Sorting & Searching

Merge sort KYA hai?

Iska genius yeh hai ki divide step mein koi bhi comparison nahi hoti — bas mid = (lo+hi)/2 hai. Saari intelligence merge mein rehti hai, jo do sorted lists ko do pointers ke saath walk karta hai.

Merging KYU kaam karta hai? (Core sub-routine)

HOW merge works (pointers i, j):
A = [1, 4, 7]    i→
B = [2, 3, 9]    j→
out = []
cmp 1,2 → take 1   out=[1]
cmp 4,2 → take 2   out=[1,2]
cmp 4,3 → take 3   out=[1,2,3]
cmp 4,9 → take 4   out=[1,2,3,4]
cmp 7,9 → take 7   out=[1,2,3,4,7]
A empty → copy 9   out=[1,2,3,4,7,9]

Diagram

Isko likhte kaise hain (Python, definition se derive karke)

def merge(A, B):
    i = j = 0
    out = []
    while i < len(A) and j < len(B):
        # <=  (not <) is what makes merge sort STABLE
        if A[i] <= B[j]:
            out.append(A[i]); i += 1
        else:
            out.append(B[j]); j += 1
    out.extend(A[i:])   # copy leftover
    out.extend(B[j:])
    return out
 
def merge_sort(a):
    if len(a) <= 1:            # base case: already sorted
        return a
    mid = len(a) // 2
    left  = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    return merge(left, right)

Running time scratch se derive karo

Yeh recurrence kyun? Half size ke do subproblems (2T(n/2)) plus linear-time merge (cn).

Recursion tree se solve karo (HOW):

• Level $0$: 1 problem of size $n$ → kaam $cn$.
• Level $1$: 2 problems of size $n/2$ → kaam $2\cdot c\frac{n}{2}=cn$.
• Level $k$: $2^k$ problems of size $n/2^k$ → kaam $2^k\cdot c\frac{n}{2^k}=cn$.

Har level $cn$ kaam karta hai. Kitne levels hain? Hum tab tak halve karte hain jab tak size $1$ na ho: $\frac{n}{2^L}=1\Rightarrow L={\log }_{2}n.$ Total levels $={\log }_{2}n+1$. Isliye $T(n)=cn({\log }_{2}n+1)=\boxed{\Theta (n\log n)}.$

Proof of correctness (induction on $n$)

$n=\text{len}(a)$ par strong induction se proof.

• Base case $n\le 1$: $0$ ya $1$ element ki list trivially sorted hai aur apna khud ka permutation hai. ✓

• Inductive hypothesis (IH): maano merge_sort $<n$ saari lengths ke liye sahi hai.

• Inductive step: length $n$ ke liye, hum left (size $\lfloor n/2\rfloor <n$) aur right (size $\lceil n/2\rceil <n$) mein split karte hain. IH se dono recursive calls apni halves ke sorted permutations return karti hain.

  Ab prove karo ki merge sahi hai (loop invariant):

  • Initialization: out=[] — vacuously true.
  • Maintenance: hum $\min (A[i],B[j])$ append karte hain, jo out mein sab se $\ge$ hai (invariant se) aur baaki sabse $\le$ (kyunki $A,B$ sorted hain). Sortedness aur bound preserve rehta hai.
  • Termination: ek list empty ho jaati hai; hum baaki copy karte hain (already sorted aur out ke sab se $\ge$). Toh out $A\cup B$ ka ek sorted permutation hai. ✓

  Isliye merge(left,right) $a$ ka ek sorted permutation return karta hai. Induction se algorithm saare $n$ ke liye sahi hai. $■$

Worked examples

Flashcards

Connections

• Divide and Conquer — woh general paradigm jiska merge sort udaharan hai.
• Quick sort — average mein $O(n\log n)$ bhi hai lekin in-place aur not stable; merge sort uska stable counterpart hai.
• Master Theorem — $T(n)=2T(n/2)+\Theta (n)$ directly solve karta hai (Case 2 ⟹ $n\log n$).
• Big-O Notation — yahan complexity bounds ki bhasha.
• Stability of Sorting Algorithms — equal-key order preserve karna kyun matter karta hai.
• Recursion and Induction — upar use ki gayi proof technique.
• External Sorting — merge sort RAM se badi data sorting ke liye base hai.

Concept Map