Merge sort: merging, recurrence, comparison counts

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Insertion sort shifts equal? from Lesson 3.1.2
• T(n) = 2T(n/2) + n? from Lesson 1.2.3
• Which sorts are stable? from Lesson 3.1.2

1 · The Hook

🎣

Merging two sorted piles is easy: repeatedly take the smaller top card. Merge sort turns that into a full sort: split the array in half, sort each half the same way, merge. It is Θ(n log n) on every input, stable, and its comparison counts are a GATE favourite.

2 · Predict First

🤔

Merge the sorted lists [2, 5, 9] and [1, 3, 7]. How many comparisons does the merge make?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

2 vs 1 → 1; 2 vs 3 → 2; 5 vs 3 → 3; 5 vs 7 → 5; 9 vs 7 → 7; right list empty, copy 9. 5 comparisons.

Merging

Two sorted lists of lengths p and q: compare the fronts, move the smaller to the output, repeat; when one list empties, copy the rest.

• At most p + q − 1 comparisons (the last element is copied without comparing).
• At least min(p, q) (when one list runs out first: [1, 2, 3] with [4, 5, 6, 7] takes 3).
• Θ(p + q) time, Θ(p + q) extra space for the output.

Merge sort

void msort(A, lo, hi) {
    if (lo >= hi) return;
    mid = (lo + hi) / 2;
    msort(A, lo, mid); msort(A, mid + 1, hi);
    merge(A, lo, mid, hi);
}

• T(n) = 2T(n/2) + Θ(n) → Θ(n log n) best, average and worst.
• Θ(n) auxiliary space (not in-place); stable (on ties, take from the left list).
• Recursion depth ⌈log n⌉.

Comparison counts

Worst case W(n) = W(⌈n/2⌉) + W(⌊n/2⌋) + n − 1, W(1) = 0. For n = 2ᵏ: W(n) = n log n − n + 1 (n = 8: 17; n = 16: 49).

Trace on A = [5, 2, 9, 1, 7, 3] (left half = first ⌊n/2⌋ elements):

• [5] [2, 9]: sort [2, 9] (1), merge with [5] (2) → [2, 5, 9]
• [1] [7, 3]: sort [7, 3] (1), merge with [1] (1) → [1, 3, 7]
• merge [2, 5, 9] with [1, 3, 7] (5)

Total 10 comparisons (the worst case for 6 is 11).

Bottom-up merge sort

Merge runs of length 1, then 2, then 4 …: ⌈log n⌉ passes, each Θ(n).

4 · Visual

[5 2 9 1 7 3]
          /                  \
      [5 2 9]              [1 7 3]
      /    \               /    \
    [5]   [2 9]          [1]   [7 3]
          /   \                /   \
        [2]   [9]            [7]   [3]
    merge up:  [2 9] -> [2 5 9]     [3 7] -> [1 3 7]
               final merge -> [1 2 3 5 7 9]

5 · Worked Examples

Example 1 Easy

Maximum comparisons to merge sorted lists of sizes 4 and 6?

Solution

4 + 6 − 1 = 9.

Example 2 Medium

Worst-case comparisons of merge sort on 16 elements?

Solution

16 × 4 − 16 + 1 = 49.

Example 3 GATE

Minimum comparisons to merge [1, 2, 3] with [4, 5, 6, 7]?

Solution

3: each of 1, 2, 3 is compared with 4, then the left list is empty.

6 · GATE Traps

⚠️

• Merging p + q elements: p + q − 1 comparisons worst, min(p, q) best.
• Merge sort is Θ(n log n) even on sorted input.
• It is stable but not in-place.
• Count comparisons level by level for exact answers; don't use n log n blindly.

7 · Memory Hook

🧠

"Split, sort, merge: take the smaller front."

8 · Connect the Dots

Merge sort does the work after the recursive calls (merging). Quicksort, next, does it before (partitioning) and needs no extra array, at the risk of a quadratic worst case.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markMerge comparisons

Merge [1, 4, 7, 10] with [2, 3, 5, 6, 8, 9]. Number of comparisons?

Numerical answer: ________

Q2NAT2 marksWorst case

Worst-case comparisons of merge sort on 8 elements?

Numerical answer: ________

Q3NAT2 marksExact trace

Merge sort (left half = first ⌊n/2⌋ elements) on [8, 7, 6, 5, 4, 3, 2, 1]. Total comparisons?

Numerical answer: ________

Q4MCQ1 markSpace and stability

Standard merge sort is:

• (A) unstable and not in-place
• (B) stable and in-place
• (C) unstable and in-place
• (D) stable and not in-place

Q5NAT1 markBottom-up passes

Bottom-up merge sort on 100 elements makes how many merging passes?

Numerical answer: ________

10 · Rule Card

• Merge p + q: ≤ p + q − 1 comparisons, ≥ min(p, q).
• Merge sort: Θ(n log n) all cases; Θ(n) extra space; stable; depth ⌈log n⌉.
• Worst comparisons W(n) = W(⌈n/2⌉) + W(⌊n/2⌋) + n − 1; n = 2ᵏ → n log n − n + 1.
• Bottom-up: ⌈log n⌉ passes.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

merging two sorted listsmerge comparisons p + q − 1merge sortworst-case comparisons n log n − n + 1bottom-up merge sort

12 · Answer Vault