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

This page assumes you've read the parent Merge sort note. We probe the same ideas — Divide and Conquer, Big-O Notation, Stability of Sorting Algorithms, Recursion and Induction — from the angle of "where do people go wrong?"

True or false — justify

Merge sort's divide step does most of the comparison work.

False. The divide step is just mid = (lo+hi)//2 — zero comparisons. All comparing happens inside merge, so merge is where the intelligence lives.

Merge sort is faster in the best case than in the worst case.

False. It always splits exactly in half and always merges in

Θ (n)

; input order can't change the recursion shape, so best = average = worst =

Θ (n lo g n)

Merge sort can be made to run in-place with no extra array.

Mostly false in practice. The standard array version needs

Θ (n)

scratch space to merge; true in-place merge algorithms exist but are complicated and slower, so we call standard merge sort "not in-place."

If both input lists to merge are sorted, the output is guaranteed sorted.

True. The overall smallest unused element is always at a front, so taking the smaller front repeatedly builds a sorted output — this is the whole loop invariant.

Using < instead of <= in merge still produces a correctly sorted array.

True — it still sorts, but it's no longer stable: on ties < grabs the right element first, swapping the original order of equal keys.

Merge sort is stable regardless of how you write the tie-break.

False. Stability depends entirely on preferring the left element on ties (<=). Change the tie-break and you lose stability.

A recurrence

T (n) = 2 T (n /2) + c n

can only come from merge sort.

False. Many divide-and-conquer algorithms share this shape; the Master Theorem solves it to

Θ (n lo g n)

for any of them, e.g. some closest-pair algorithms.

Merge sort does

Θ (n lo g n)

comparisons on every input, exactly.

False about "exactly." It does

Θ (n lo g n)

comparisons, but the exact count varies with input; e.g. an already-sorted input triggers fewer comparisons per merge (one list exhausts early).

Doubling the input size roughly doubles merge sort's running time.

False (slightly more). Going

n \to 2 n

multiplies work by

2 \cdot \frac{l o g 2 n}{l o g n} > 2

; it adds one extra merge layer, so it's a bit more than double.

Merge sort and Quick sort have the same worst-case time.

False. Merge sort is

Θ (n lo g n)

worst-case; quicksort degrades to

Θ (n^{2})

on bad pivots. Merge sort's guarantee is its selling point.

Spot the error

"Merge needs the whole combined list to be sorted before it can work."

Wrong. Merge needs each input half sorted, not the combination — producing the sorted combination is merge's job, guaranteed by the recursion's induction hypothesis.

"Merge sort is

O (n^{2})

because it makes

n

recursive calls."

Wrong. There are about

2 n

calls total, but the work is

c n

per level over

lo g n

levels, giving

Θ (n lo g n)

— you must count work, not call count.

"After

n - 1

comparisons in a merge of total length

n

, we may still need more comparisons."

Wrong. After at most

n - 1

comparisons one list is empty; the remaining elements are copied with no comparisons, since there's nothing left to compare against.

"The base case can be size

0

only; a size-1 list still needs sorting."

Wrong. A list of size

\leq 1

is already sorted (nothing to reorder), so both size

0

and size

1

are valid, no-op base cases.

"To prove correctness we only need the base case and the merge invariant."

Wrong / incomplete. You also need the inductive hypothesis that both recursive calls return sorted halves; without assuming smaller cases are correct, the invariant has no sorted inputs to rely on.

"Merge sort halves the input, so it must have exactly

lo g_{2} n

recursive levels for all

n

Wrong for non-powers-of-2. The depth is

⌈ lo g_{2} n ⌉

; when

n

isn't a power of two, halves are

⌊ n /2 ⌋

and

⌈ n /2 ⌉

, so levels round up.

"Since the divide step is free, merge sort's cost is dominated by dividing."

Wrong / contradictory. Dividing being free means it's not the cost driver — the merging (the cn term) dominates the recurrence.

Why questions

Why is the front of a sorted list always where the next-smallest element hides?

Because the list is sorted, everything behind the front is

\geq

the front; so no unused element smaller than the front can exist in that list.

Why does merge sort trade insertion sort's

n^{2}

for

n lo g n

Insertion sort does

n

passes each costing up to

n

; merge sort does only

lo g n

merge layers, each costing

n

— far fewer, cheaper layers.

Why must we prefer the left element on ties for stability?

Equal keys from the left half were earlier in the original array; taking left-first preserves that original relative order, which is exactly what stability means.

Why is the recurrence

2 T (n /2) + c n

and not

2 T (n /2) + c

The merge step touches all

n

elements once, so its cost grows linearly with

n

(the

c n

), not as a constant.

Why does every level of the recursion tree do the same

c n

work?

At level

k

there are

2^{k}

subproblems each of size

n / 2^{k}

; multiplying gives

2^{k} \cdot c n / 2^{k} = c n

, independent of

k

Why do we use strong induction rather than ordinary induction for correctness?

The two halves have sizes

⌊ n /2 ⌋

and

⌈ n /2 ⌉

— both smaller than

n

but not equal to

n - 1

; strong induction lets us assume correctness for all smaller sizes at once.

Why is merge sort a natural fit for External Sorting (data too big for memory)?

Merge only ever streams through inputs front-to-back with pointers, so it reads sorted runs sequentially from disk — perfect for slow, sequential-access storage.

Edge cases

What does merge sort do on an empty array []?

It hits the base case (len <= 1) immediately and returns [] — already sorted, a valid permutation of itself.

What happens when merging where one input list is empty?

The while loop doesn't run (one pointer is past the end); the non-empty list is copied wholesale — still sorted, zero comparisons.

What if all elements are equal, e.g. [5,5,5,5]?

Every comparison is a tie; with <= the left element always wins, so relative order is preserved and the output is trivially sorted — a clean stability stress-test.

What if the array is already sorted?

Merge sort still fully recurses and merges (structure is input-independent), so it's still

Θ (n lo g n)

— unlike insertion sort, it can't exploit pre-sortedness.

What if the array is sorted in reverse?

Same

Θ (n lo g n)

— the divide/merge structure never changes; reverse input is not a worst case for merge sort the way it is for others.

What happens for an odd length like n = 5?

mid = 5//2 = 2 splits into sizes

2

and

3

; both are

< 5

, so recursion still shrinks and terminates — halving need not be exactly even.

Does the two-pointer merge ever compare an element to itself?

No. The pointers i and j index different lists, so A[i] and B[j] are always distinct list positions — a single element is never compared to itself.

Recall One-line self-test

If you can answer "what breaks if I change <= to <?" and "why is every level $c n$ work?" without peeking, you own this topic. What breaks with <? ::: Stability breaks — equal keys swap order; correctness/sorting survives. Why is every level $c n$ ? ::: $2^{k}$ pieces times size $n / 2^{k}$ cancels to $c n$ regardless of depth.

Connections

Parent: Merge sort — the full derivation these traps target.
Stability of Sorting Algorithms — why the <= tie-break matters.
Recursion and Induction — the proof machinery behind correctness.
Master Theorem / Big-O Notation — solving and naming the $Θ (n lo g n)$ cost.
Quick sort · External Sorting · Divide and Conquer — comparison points.