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

Parent: Merge sort (Hinglish). This is the visual walkthrough.

Step 1 — The one thing that is easy: merging two sorted lists

WHAT. Forget sorting for a moment. Suppose someone hands you two lists that are already sorted — smallest first. Call them $A$ and $B$ . We want one combined list, also sorted.

WHY this first. The whole algorithm rests on one cheap trick. If we understand merging deeply, everything else is just "cut things up so we can merge." So we start at the trick.

Here is the trick in one sentence: the smallest number you have not yet used must be sitting at the front of $A$ or the front of $B$ . It cannot hide in the middle, because everything behind a front is bigger-or-equal to that front (the lists are sorted). So you only ever look at two numbers at a time.

We track our place with two pointers — think of them as two fingers, one resting on the current front of each list. We name them $i$ (finger on $A$ ) and $j$ (finger on $B$ ).

PICTURE.

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

The cyan finger $i$ points at $A [i]$ , the smallest unused value of $A$ .
The amber finger $j$ points at $B [j]$ , the smallest unused value of $B$ .
We compare only these two, take the smaller into out, and slide that one finger right.

Step 2 — One merge step, drawn term by term

WHAT. Do a single comparison and see exactly what moves.

WHY. Before counting the whole cost we must be sure each step is cheap and correct. One picture nails both.

The rule, written out:

$take min (front of A A [i], front of B B [j]) \to append to out, then slide that finger$

Reading it: $A [i]$ is whatever the cyan finger sits on; $B [j]$ is whatever the amber finger sits on; $min$ picks the smaller of the two; that value gets written to the output list out; the finger that gave the value moves one step right so it now points at the next unused value.

On ties ( $A [i] = B [j]$ ) we deliberately take from $A$ (the left list). This one choice is what makes merge sort stable — equal items keep their original left-to-right order. Hold that thought; Step 6 makes it visual.

PICTURE.

Step 3 — But the input is messy. So: cut it in half

WHAT. Real input is not sorted. We cannot merge yet. So we divide: split the array into a left half and a right half at the midpoint.

WHY. Merging needs sorted inputs. We do not have them — so we manufacture them by making the problem smaller. Cutting costs almost nothing: it is a single arithmetic line.

$mid = ⌊ \frac{n}{2} ⌋$

Term by term: $n$ is the current length; $\frac{n}{2}$ is the halfway point; the floor brackets $⌊ ⌋$ mean "round down to a whole index" (you cannot split at index $2.5$ ). The left half is positions $0 \dots mid - 1$ ; the right half is $mid \dots n - 1$ .

Crucially the divide step does no comparisons — it is pure bookkeeping. All the brain-work stays in the merge from Steps 1–2.

PICTURE.

This is the Divide and Conquer idea: shrink until trivial, then combine.

Step 4 — Keep cutting until every piece is trivially sorted

WHAT. Apply the cut again to each half. And again. Stop when a piece has length $\leq 1$ .

WHY. A list with one element is already sorted — there is nothing to compare it against. So size $1$ is our base case: the point where recursion stops and merging can begin.

PICTURE.

Notice the shape: each level doubles the number of pieces and halves their size. That symmetry is the seed of the whole cost analysis — remember it for Step 7.

Step 5 — Now merge back up the tree

WHAT. From the row of singletons, run the Step-2 merge to glue pairs back together — then glue those results, and so on, until one sorted list remains.

WHY. Each merge needs sorted inputs. Singletons are sorted (Step 4), so the first merge layer is legal; its outputs are sorted, so the next layer is legal; induction carries us all the way up. We trust the sub-results — we never re-check them.

PICTURE.

Follow the amber arrows upward: [5],[2] → [2,5]; [4],[1] → [1,4]; then the two sorted pairs [2,5] and [1,4] merge into [1,2,4,5]. Every arrow is one application of the cheap trick from Step 2.

Step 6 — The edge case that hides in plain sight: equal keys (stability)

WHAT. What happens when two elements are equal? Say we sort records by their number, and two records both have key $3$ : a left one $(3, a)$ and a right one $(3, c)$ .

WHY it deserves its own step. Every other case is a strict $<$ or $>$ ; the tie is the one moment the algorithm makes a choice, and that choice decides whether merge sort is stable. Missing this case is the #1 beginner bug.

The comparison in code is A[i] <= B[j] — note the $\leq$ , not $<$ . On a tie, $\leq$ is true, so we take from the left list $A$ first.

$A [i] \leq B [j] \Rightarrow take left ⟺ equal records keep original order$

Reading it: when the two fronts are equal, <= still fires and we emit the left one; had we written <, the tie would fall to the else branch and we would emit the right one first — silently swapping two equal records.

PICTURE.

Step 7 — Count the work: build $n lo g n$ from the picture

WHAT. We now count total comparisons+writes, level by level, using the tree from Step 4.

WHY this way. We do not guess the answer — we read it off the picture. Two facts, each visible in the tree, multiply together.

Fact 1 — every level costs $c n$ . At level $k$ there are $2^{k}$ pieces, each of size $n / 2^{k}$ . Merging all of them costs:

$how many pieces 2^{k} \times cost per piece c \frac{n}{2 ^{k}} = c n .$

The $2^{k}$ and the $1/ 2^{k}$ cancel — that is the magic. Whatever level you are on, the total merge work across that whole row is the same: $c n$ . (Here $c$ is just a fixed constant "cost per element" hidden inside $Θ (n)$ .)

Fact 2 — how many levels are there? We halve $n$ until we reach size $1$ :

$\frac{n}{2 ^{L}} = 1 ⟹ 2^{L} = n ⟹ L = lo g_{2} n .$

Multiply the two facts:

$T (n) = per level c n \times number of levels (lo g_{2} n + 1) = Θ (n lo g n) .$

The $+ 1$ counts the top level (size $n$ ) itself; it disappears inside $Θ$ (see Big-O Notation).

PICTURE.

Recall Why not

$n^{2}$ like insertion sort? Insertion sort does $n$ passes, each up to $n$ work → $n^{2}$ . Merge sort does only $lo g n$ layers, each $n$ work → $n lo g n$ . We traded a few extra layers for cheap linear merges. " $n$ wide, $lo g n$ tall."

Step 8 — The degenerate inputs: does it still work?

WHAT. Push the algorithm to its limits and check nothing breaks.

WHY. A derivation is only trustworthy if it survives the corners: empty lists, one element, all-equal elements, already-sorted, reverse-sorted.

Input	What the tree does	Result
$n = 0$ (empty)	base case fires immediately, no merges	returns `[]` ✓
$n = 1$	base case, already sorted	returns as-is ✓
all equal, e.g. `[3,3,3,3]`	ties everywhere → `<=` keeps left order	sorted and stable ✓
already sorted	still splits fully, still merges	$Θ (n lo g n)$ — no early exit!
reverse sorted	same structure	$Θ (n lo g n)$

PICTURE.

Recall Best = average = worst

Notice rows 4 and 5: merge sort cannot shortcut on nice input — it always cuts fully and always merges fully. So best = average = worst = $Θ (n lo g n)$ . The trade-off is $Θ (n)$ extra memory (a scratch array to merge into) — not in-place. When the data is too big for memory, this same merge idea powers External Sorting. Contrast Quick sort, which is input-sensitive and can degrade to $n^{2}$ .

The one-picture summary

Everything on this page in one frame: cut down (free, no comparisons), hit size-1 base cases (trivially sorted), then merge up (the cheap two-finger trick). Each of the $lo g_{2} n$ horizontal bands costs $c n$ ; multiply → $Θ (n lo g n)$ .

Recall Feynman: tell it to a 12-year-old

You have a shuffled deck. Splitting it in half is lazy — you just cut, no thinking. Keep cutting until every "pile" is a single card. A single card is already in order, so now the clever part begins. Two friends each hold a small sorted pile; to combine them, they keep flipping over the smaller top card into a new pile — that is easy because they only ever look at the two tops. They do this over and over, combining bigger and bigger sorted piles, until one sorted deck remains. Why is it fast? Because the height of all this cutting is tiny — you can only halve a deck about $lo g n$ times — and each combining pass just walks past every card once. Tall by a little, wide by everything: $n$ times $lo g n$ . And the golden rule when two cards tie: the left one goes down first, so equal cards never secretly swap — that is what "stable" means.

Connections

Divide and Conquer — the paradigm this whole picture is an instance of.
Recursion and Induction — why "trust the sub-results" is valid.
Master Theorem — the shortcut for the Step-7 recurrence.
Big-O Notation — what $Θ$ and the vanishing $+ 1$ mean.
Stability of Sorting Algorithms — the Step-6 "lefty wins" choice.
Quick sort · External Sorting — where this idea goes next.