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

WHAT is merge sort?

The genius is that the divide step does no comparisons at all — it's just mid = (lo+hi)/2. All the intelligence lives in merge, which walks two sorted lists with two pointers.

WHY does merging work? (The 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]

The diagram

HOW to write it (Python, derived from the definition)

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)

Derive the running time from scratch

Why this recurrence? Two subproblems of half the size (the 2T(n/2)) plus a linear-time merge (cn).

Solve by the recursion tree (HOW):

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

Every level does $cn$ work. How many levels? We halve until size $1$: $\frac{n}{2^L}=1 \;\Rightarrow\; L=\log_2 n.$ Total levels $=\log_2 n + 1$. Therefore $T(n)=cn\,(\log_2 n + 1)=\boxed{\Theta(n\log n)}.$

Proof of correctness (induction on $n$)

Proof by strong induction on $n=\text{len}(a)$.

• Base case $n\le 1$: a list of $0$ or $1$ element is trivially sorted and is its own permutation. ✓

• Inductive hypothesis (IH): assume merge_sort is correct for all lengths $< n$.

• Inductive step: for length $n$, we split into left (size $\lfloor n/2\rfloor < n$) and right (size $\lceil n/2\rceil < n$). By IH both recursive calls return sorted permutations of their halves.

  Now prove merge is correct (loop invariant):

  • Initialization: out=[] — vacuously true.
  • Maintenance: we append $\min(A[i], B[j])$, which is $\ge$ everything in out (by invariant) and $\le$ all remaining (since $A,B$ sorted). Sortedness and the bound are preserved.
  • Termination: one list empties; we copy the rest (already sorted and $\ge$ all of out). So out is a sorted permutation of $A\cup B$. ✓

  Hence merge(left,right) returns a sorted permutation of $a$. By induction the algorithm is correct for all $n$. $\blacksquare$

Worked examples

Flashcards

Connections

• Divide and Conquer — the general paradigm merge sort exemplifies.
• Quick sort — also $O(n\log n)$ average but in-place and not stable; merge sort is the stable counterpart.
• Master Theorem — solves $T(n)=2T(n/2)+\Theta(n)$ directly (Case 2 ⟹ $n\log n$).
• Big-O Notation — language for the complexity bounds here.
• Stability of Sorting Algorithms — why preserving equal-key order matters.
• Recursion and Induction — the proof technique used above.
• External Sorting — merge sort underlies sorting data too big for RAM.

Concept Map

Hinglish (regional understanding)