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

The line if A[i] <= B[j]:. The <= means: on a tie, take the LEFT list's element first. Since the left list holds elements that came earlier in the original array, equal keys stay in original order — that's exactly stability. Change it to < and on a tie you'd take the right element first, swapping equal records → not stable.

Correct order: Divide → Conquer → Combine.

• Divide splits at mid = len//2 — this does zero comparisons, just arithmetic.
• Conquer recursively sorts each half.
• Combine = merge, where all the comparisons actually happen.

Best = Average = Worst = $\Theta (n\log n)$; Space $=\Theta (n)$ (extra array). Why best = worst: the structure never changes with input — merge sort always splits exactly in half and always merges in $\Theta (n)$ regardless of whether the input is already sorted, reversed, or random. See Big-O Notation.

Refer to the recursion tree in the figure below.

1. Split [8,3,5,1] → [8,3] and [5,1] (mid = 4//2 = 2).
2. [8,3] → [8],[3]; merge: cmp 8 vs 3 → 3 smaller → [3,8].
3. [5,1] → [5],[1]; merge: cmp 5 vs 1 → 1 smaller → [1,5].
4. Merge [3,8] & [1,5]:
   • cmp 3 vs 1 → take 1 → [1]
   • cmp 3 vs 5 → take 3 → [1,3]
   • cmp 8 vs 5 → take 5 → [1,3,5]
   • right list empty → copy 8 → [1,3,5,8] ✓

Using <= (prefer left = $A$ on ties):

• cmp $2_a\le 2_b$? yes → take $2_a$ → out $=[2_a]$
• cmp $2_a^{\prime }\le 2_b$? yes → take $2_a^{\prime }$ → out $=[2_a,2_a^{\prime }]$
• cmp $6\le 2_b$? no → take $2_b$ → out $=[2_a,2_a^{\prime },2_b]$
• cmp $6\le 4$? no → take $4$ → out $=[2_a,2_a^{\prime },2_b,4]$
• $B$ empty → copy $6$ → $[2_a,2_a^{\prime },2_b,6,4]$… wait, careful: after taking 4, $B$ is empty, then copy leftover of $A$ = $[6]$.
• Final: $[2_a,2_a^{\prime },2_b,4,6]$. All of $A$'s twos ($2_a,2_a^{\prime }$) come before $B$'s two ($2_b$) → stability preserved. See Stability of Sorting Algorithms.

Layers to reach size 1: ${\log }_{2}16=4$, plus the size-1 base level → total depth ${\log }_{2}n+1=5$ levels. Each level does $cn$ work (level $k$ has $2^k$ problems of size $n/2^k$, and $2^k\cdot c\frac{n}{2^k}=cn$). So total $\approx cn({\log }_{2}n+1)=16c\cdot 5=80c$, i.e. $\Theta (n\log n)$.

Maximum $=n-1$. Proof: every comparison outputs at least one element (the smaller front). After $k$ comparisons, at least $k$ elements are placed. The loop stops the moment one list empties; at worst that happens right after the second-to-last element is placed, i.e. after $n-1$ comparisons. The final remaining element is copied with no comparison. Hence at most $n-1$. Worst case is achieved when the two lists interleave perfectly, e.g. $A=[1,3,5]$, $B=[2,4,6]$.

Trace: cmp(1,2)→1; cmp(3,2)→2; cmp(3,4)→3; cmp(5,4)→4; cmp(5,6)→5; then $A$ empty, copy 6 (no cmp). That's 5 comparisons, and $n-1=6-1=5$. ✓ Perfect interleaving forces the maximum.

• Insertion (worst): $\frac{n^2}{2}=\frac{1024^2}{2}=\frac{1,048,576}{2}=524,288$.
• Merge (upper bound): $n{\log }_{2}n=1024\times 10=10,240$.
• Ratio $=\frac{524,288}{10,240}=51.2$. Merge sort does about 51× fewer comparisons here. This gap is the whole point of $n\log n$ vs $n^2$.

During merge, when you take an element from the right list B[j] while the left list A still has $\text{len}(A)-i$ elements remaining, every one of those remaining left elements is greater than B[j] (both lists sorted) — so add $\text{len}(A)-i$ to the inversion count.

Trace on $[2,4,1,3,5]$ (true inversions: $(2,1),(4,1),(4,3)$ = 3):

• Split → $[2,4]$ and $[1,3,5]$ (deeper merges within each half add 0 inversions here since each is already sorted).
• Merge $[2,4]$ (left, $i$) with $[1,3,5]$ (right, $j$):
  • cmp 2 vs 1 → take 1 from right; left has 2 elements remaining → add 2.
  • cmp 2 vs 3 → take 2 from left.
  • cmp 4 vs 3 → take 3 from right; left has 1 element (the 4) remaining → add 1.
  • cmp 4 vs 5 → take 4 from left.
  • right leftover 5 → copy.
• Total inversions $=2+1=3$. ✓ Matches the brute-force count.

This is external sorting — see External Sorting.

• Divide/Conquer: read the file in chunks that do fit in RAM (say 4 GB each → 25 chunks), sort each chunk in memory, write each back as a sorted "run" on disk.
• Combine: do a $k$-way merge of the 25 sorted runs. Merge only needs the front of each run in memory at a time — exactly the two-pointer idea generalized to $k$ pointers. You stream elements out to the final file, always emitting the smallest current front. Merge sort's key property — that merging needs only sorted inputs, never the whole thing in memory — is precisely what makes it the algorithm of choice for data too big for RAM. (Quicksort, which needs random access, does not adapt as cleanly — see Quick sort.)

Merge loop invariant: before each iteration, out is sorted and every element of out is $\le$ every unconsumed element of both inputs.

• Init: out=[] — vacuously true.
• Maintenance: we append $\min (A[i],B[j])$. It is $\ge$ everything already in out (invariant) and $\le$ all remaining (inputs sorted). Both properties survive.
• Termination: one list empties; the leftover is already sorted and $\ge$ all of out, so out becomes a sorted permutation of $A\cup B$. ✓

Strong induction on $n$:

• Base $n\le 1$: trivially sorted, its own permutation. ✓
• IH: assume correctness for all lengths $<n$.
• Step: split into left of size $\lfloor n/2\rfloor$ and right of size $\lceil n/2\rceil$, both $<n$. The one place the IH is used is here: we assert both recursive calls return sorted permutations — that's licensed by IH because both sizes are strictly less than $n$. Then merge (proven correct above) fuses them. $■$

Why weak induction fails: weak induction only gives you correctness for $n-1$. But the recursive calls have size $\approx n/2$, which for $n\ge 3$ is not $n-1$. You'd have no license to assume the size-$n/2$ calls are correct. Strong induction (all sizes $<n$) is exactly what covers the $n/2$ subproblems. See Recursion and Induction.

Master Theorem form: $T(n)=aT(n/b)+f(n)$ with $a=2$, $b=2$, $f(n)=cn=\Theta (n^1)$. Compute the watershed exponent ${\log }_{b}a={\log }_{2}2=1$. Compare $f(n)=\Theta (n^1)$ with $n^{{\log }_{b}a}=n^1$: they're the same order → Case 2. Case 2 gives $T(n)=\Theta \left(n^{{\log }_{b}a}\log n\right)=\Theta (n\log n)$. ✓ Identical to the recursion-tree result.

• Sortedness: ✅ true — with <, ties are still resolved (just favoring the right element), and the output is still non-decreasing. So if the spec is "return a sorted permutation," < is correct.
• Stability spec: ❌ broken — if the spec additionally requires "equal keys keep original order," then < violates it by taking right-half equals first. Resolution: there's no contradiction — correctness is relative to a specification. < satisfies the weaker (sorted-only) spec but not the stronger (sorted + stable) spec. The parent note's algorithm uses <= precisely to meet the stronger spec.