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

This page hunts down every kind of input merge sort can meet — not just the pretty ones. We start with a map of all the cases, then work each one fully so you never hit a surprise on an exam.

See the parent for the full theory: Merge sort — divide and conquer, O(n log n), stable.

The scenario matrix

Cell	Case class	What could go wrong / why it matters	Covered by
A	Empty / single element (degenerate)	Base case — does recursion even stop?	Ex 1
B	Odd length (uneven split)	`mid = n//2` splits $3 \to 1 + 2$ ; do we lose an element?	Ex 2
C	Already sorted (best-looking input)	Does merge do wasted work? Is it still $Θ (n lo g n)$ ?	Ex 3
D	Reverse sorted (worst-looking input)	Every comparison "loses" — max shuffling	Ex 4
E	All equal / ties (stability corner)	Does order of equal keys survive?	Ex 5
F	Duplicates + `<` vs `<=` (stability break)	The one line that makes or breaks stability	Ex 6
G	Exact comparison count (limiting/counting)	Best-case vs worst-case comparisons for fixed $n$	Ex 7
H	Real-world word problem (external merge)	Merging two sorted files too big for memory	Ex 8
I	Exam twist (count inversions via merge)	Reuse the merge to solve a different problem	Ex 9

Every numeric answer below is machine-checked at the bottom.

Cell A — the degenerate base cases

Cell B — odd length, uneven split

Worked example Example 2 — full trace of

[3, 1, 2] (odd length) Forecast: with 3 elements, mid = 3 // 2 = 1. Predict the split before reading.

mid = 1, so left = [3], right = [1, 2]. Why this step? // is integer division — it rounds down, giving a smaller left half and larger right half. No element is lost: $1 + 2 = 3$ .
left = [3] is size 1 → returns [3] (base case). Why this step? Already sorted.
right = [1, 2] splits into [1] and [2], merges: compare $1$ vs $2$ , take $1$ , then copy $2$ → [1, 2]. Why this step? $1 \leq 2$ , so left (which is $1$ ) goes out first.
Merge [3] and [1, 2]: compare $3$ vs $1$ → take $1$ ; compare $3$ vs $2$ → take $2$ ; left-of-merge (the $1, 2$ list) empty, copy $3$ → [1, 2, 3]. Why this step? The two-pointer walk always takes the smaller front.

Verify: [1,2,3] is a permutation of [3,1,2] and sorted ✓. Comparisons used: 1 (in step 3) + 2 (in step 4) $= 3$ .

See the recursion tree for this odd split:

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

Cell C — already-sorted input (does it waste work?)

Worked example Example 3 —

[1, 2, 3, 4] already sorted Forecast: does merge sort "notice" it's sorted and skip work, like insertion sort would?

Split → [1,2] and [3,4]. Why this step? The divide step never looks at values, only positions. It cannot notice sortedness.
[1,2] → merge [1],[2]: compare $1 \leq 2$ → [1,2] (1 comparison). Same for [3,4] → [3,4] (1 comparison). Why this step? Structure is fixed regardless of input.
Merge [1,2] and [3,4]: compare $1$ vs $3$ → take $1$ ; compare $2$ vs $3$ → take $2$ ; left half empty → copy [3,4]. That's 2 comparisons, then the rest copied. Why this step? Once one list empties, the leftover is appended with no comparisons — this is why sorted input hits the low comparison count.

Verify: result [1,2,3,4] ✓. Total comparisons $= 1 + 1 + 2 = 4$ . Note: even the "easy" input still does full $Θ (n lo g n)$ structure — merge sort does not short-circuit like insertion sort. This is why best = worst = average (see Master Theorem).

Cell D — reverse-sorted input (maximum shuffling)

Worked example Example 4 —

[4, 3, 2, 1] reversed Forecast: guess whether this uses more comparisons at the final merge than Example 3.

Split → [4,3] and [2,1]. Why this step? Positional split, values ignored.
[4,3] merges to [3,4] (1 comparison: $4 \leq 3$ ? no, take $3$ , then copy $4$ ). [2,1] merges to [1,2] (1 comparison). Why this step? Each pair needs exactly one comparison.
Merge [3,4] and [1,2]: compare $3$ vs $1$ → take $1$ ; compare $3$ vs $2$ → take $2$ ; now right list empty → copy [3,4]. That's 2 comparisons. Why this step? After the smaller list [1,2] drains, [3,4] is copied comparison-free.

Verify: result [1,2,3,4] ✓. Total comparisons $= 1 + 1 + 2 = 4$ — same as the sorted case at $n = 4$ here. The comparison count varies only within the $[n /2, n - 1]$ band per merge; the $Θ (n lo g n)$ never changes. Reverse input is not a "worst case" for merge sort the way it is for insertion sort.

Cell E — all-equal keys (stability corner)

Worked example Example 5 —

[(2,x), (2,y), (2,z)], sort by number Here each record is (key, tag); we sort by key only, comparing keys with <=.

Forecast: will the tags come out as x, y, z (original order) or scrambled?

Split → [(2,x)] and [(2,y),(2,z)]. Why this step? mid = 3//2 = 1.
[(2,y),(2,z)] merges: compare key $2 \leq 2$ ? Yes → take the left one (2,y) first, then (2,z) → [(2,y),(2,z)]. Why this step? The <= (not <) sends the left element out on a tie, keeping y before z.
Merge [(2,x)] and [(2,y),(2,z)]: compare key $2 \leq 2$ ? Yes → take left (2,x) first, then the rest → [(2,x),(2,y),(2,z)]. Why this step? Again <= keeps the earlier (left-half) record ahead.

Verify: tags come out x, y, z = original order ✓ ⟹ stable. See Stability of Sorting Algorithms. If we had used <, step 2 would take (2,z)? No — < is false for $2 < 2$ , so it takes the right front (2,z) first ⟹ order becomes z, y — scrambled. That's Example 6.

Cell F — the `<` vs `<=` stability break

Worked example Example 6 — same input, wrong operator

Replace A[i] <= B[j] with A[i] < B[j] and re-sort [(2,x),(2,y),(2,z)].

Forecast: guess the final tag order under <.

Split → [(2,x)] and [(2,y),(2,z)]. Why this step? Split is unaffected by the operator.
Merge [(2,y)] and [(2,z)]: test A[i] < B[j] i.e. $2 < 2$ → false → take the right element (2,z) first, then (2,y) → [(2,z),(2,y)]. Why this step? On a tie, < prefers the right element — this is exactly the bug.
Merge [(2,x)] with [(2,z),(2,y)]: $2 < 2$ false → take right (2,z); then $2 < 2$ false → take (2,y); then copy (2,x) → [(2,z),(2,y),(2,x)]. Why this step? Every tie flips to the right, reversing equal records.

Verify: tags come out z, y, x = reversed ✗ ⟹ not stable. Same keys, same values sorted — but original ordering destroyed. Lesson: "Lefty wins ties" (<=) is what preserves stability. Quick sort has this problem structurally — see Quick sort.

Cell G — exact comparison counts (best vs worst of a single merge)

Worked example Example 7 — comparisons to merge two sorted lists of length 4 each

Lists $A, B$ each have 4 elements; total $n = 8$ .

Forecast: what's the fewest and most comparisons one merge can use?

Fewest: if every element of $A$ is $\leq$ every element of $B$ (e.g. $A = [1, 2, 3, 4]$ , $B = [5, 6, 7, 8]$ ), we compare $4$ (the front of $A$ ) against $5$ , take from $A$ ... we compare $A$ 's front against $B$ 's front once per $A$ -element until $A$ drains. That's $4$ comparisons, then copy all of $B$ . Why this step? Once one list empties, the rest is copied comparison-free. Minimum $= min (∣ A ∣, ∣ B ∣) = 4$ .
Most: if the lists interleave down to the last elements (e.g. $A = [1, 3, 5, 7]$ , $B = [2, 4, 6, 8]$ ), every take except the very last needs a comparison. Why this step? The most comparisons is $∣ A ∣ + ∣ B ∣ - 1 = 7$ , because after $7$ comparisons only one element remains and it's copied.

Verify: minimum comparisons $= 4$ , maximum $= 7$ for merging $4 + 4$ ✓. General band: $[min (a, b), a + b - 1]$ . Consistent with parent's " $n - 1$ comparisons" upper bound (here $8 - 1 = 7$ ). See Big-O Notation.

Cell H — real-world word problem (external merge)

Worked example Example 8 — merging two sorted phone-number files

You have two files, each already sorted, of $3$ million and $5$ million phone numbers, but only enough RAM to hold a few numbers at a time. Produce one sorted file. How many number-comparisons at most, and why can you do it with tiny memory?

Forecast: guess whether you need to load both files fully into memory.

Keep just two pointers: the current smallest-unwritten number from each file (read one at a time from disk). Why this step? The merge invariant says the global smallest unused number sits at the front of one of the two sorted streams — so you only ever need to see two numbers at once.
Compare the two current numbers, write the smaller to the output file, advance that file's read. Why this step? This is the two-pointer merge, but the "lists" live on disk. This is exactly External Sorting.
When one file ends, stream-copy the remainder of the other. Why this step? Leftover is already sorted and larger than everything written.
Total numbers $n = 3, 000, 000 + 5, 000, 000 = 8, 000, 000$ . Max comparisons $= n - 1 = 7, 999, 999$ . Why this step? Same $n - 1$ bound: each comparison outputs at least one number, and the last is copied free.

Verify: $n = 8, 000, 000$ , max comparisons $= 7, 999, 999$ ✓. Memory used $= O (1)$ numbers (plus buffers), not $O (n)$ — this is why merge is the heart of sorting data larger than RAM.

Cell I — exam twist: count inversions using merge

Worked example Example 9 — count inversions in

[2, 4, 1, 3, 5] An inversion is a pair $(i, j)$ with $i < j$ but $a_{i} > a_{j}$ (a "wrongly ordered" pair). Count them by piggy-backing on merge.

Forecast: guess the count by eye, then verify with the merge method.

By hand, list wrong-order pairs: $(2, 1), (4, 1), (4, 3)$ . Why this step? Sanity target: $3$ inversions.
Merge trick: during a merge, when we take an element from the right half while $k$ elements still remain in the left half, those $k$ left elements are all greater than the taken one (both halves sorted) ⟹ add $k$ to the count. Why this step? Every left element still waiting is bigger than a right element we output now — each is one inversion, counted in bulk.
Sort-and-count: [2,4] & [1,3,5]... total counted across all merges $= 3$ . Why this step? The recursion counts cross-half inversions at each level; within-half ones are counted deeper down. Summing all levels gives every inversion once, in $Θ (n lo g n)$ instead of the naive $Θ (n^{2})$ .

Verify: merge-based count $= 3 =$ hand count ✓. This is a classic exam question: "modify merge sort to count inversions" — the answer is "add the left-remaining count each time you pull from the right." Uses Recursion and Induction.

Recall Quick self-test

Which cell forces <= over <? ::: Cell E/F — ties, for stability. Does already-sorted input make merge sort faster asymptotically? ::: No — best = worst = $Θ (n lo g n)$ ; structure is input-independent. Fewest comparisons to merge lists of length $a$ and $b$ ? ::: $min (a, b)$ (one list fully precedes the other). Most comparisons to merge lengths $a, b$ ? ::: $a + b - 1$ . How does merge count inversions? ::: Add the number of left-half elements remaining each time you take from the right half.

Connections

Parent: Merge sort theory & proof
Divide and Conquer — the paradigm every example above rides on.
Stability of Sorting Algorithms — Cells E and F live here.
External Sorting — Cell H's real-world merge.
Big-O Notation · Master Theorem — where the counts become asymptotics.
Quick sort — contrast: not stable, not input-independent.