Merge Sort — Divide & Conquer Sorting

One of Merge Sort's most valuable properties is its guaranteed O(n log n) time complexity—regardless of input arrangement. Unlike Quick Sort, which degrades to O(n²) on pathological inputs, or Insertion Sort, which varies between O(n) and O(n²) based on initial order, Merge Sort always performs the same number of operations for arrays of the same size.

This consistency makes Merge Sort suitable for applications where predictable performance is critical—real-time systems, database operations, and any context where worst-case guarantees matter more than average-case optimization.

To analyze Merge Sort's time complexity, we express its runtime as a recurrence relation—an equation that defines the runtime for problem size n in terms of the runtime for smaller problem sizes.

Analyzing the algorithm's structure:

def merge_sort(arr):
    if len(arr) <= 1:           # O(1) - base case check
        return arr
    mid = len(arr) // 2         # O(1) - compute midpoint
    left = merge_sort(arr[:mid]) # T(n/2) - recurse on left half
    right = merge_sort(arr[mid:])# T(n/2) - recurse on right half
    return merge(left, right)   # O(n) - merge the halves

Deriving the recurrence:

Let T(n) represent the time to sort an array of n elements. From the code:

1. Base case: T(1) = O(1) — single elements require constant time
2. Recursive case: For n > 1:
   • Two recursive calls on arrays of size n/2: 2T(n/2)
   • Merge operation on n elements: O(n)
   • Divide and other overhead: O(1)

The Merge Sort recurrence:

T(n) = 2T(n/2) + O(n)
T(1) = O(1)

Or more precisely, with constants:

T(n) = 2T(n/2) + cn    (for some constant c > 0)
T(1) = d               (for some constant d > 0)

The recursion tree method provides an intuitive visual proof by examining the work done at each level of recursion.

Analyzing the tree:

Level counting:

• Level 0: 1 problem of size n
• Level 1: 2 problems of size n/2
• Level 2: 4 problems of size n/4
• Level k: 2^k problems of size n/2^k

When do we reach the base case? We reach size 1 when n/2^k = 1, which gives k = log₂(n). So there are log₂(n) + 1 levels (including level 0).

Work per level: At level k:

• Number of subproblems: 2^k
• Size of each subproblem: n/2^k
• Merge cost per subproblem: c × (n/2^k)
• Total cost at level k: 2^k × c × (n/2^k) = cn

Key insight: The work at every level is exactly cn—the same regardless of level!

Total work:

• Number of levels: log₂(n) + 1
• Work per level: cn
• Total: cn × (log₂(n) + 1) = O(n log n)

The substitution method (also called the "guess and verify" method) involves guessing the form of the solution and proving it correct by induction.

Step 1: Make an educated guess

Based on our recursion tree analysis, we guess that T(n) = O(n log n).

More precisely, we hypothesize: T(n) ≤ cn log n for some constant c > 0 and all n ≥ 2.

Step 2: Prove by strong induction

Base case: For n = 2: T(2) = 2T(1) + 2c₁ = 2d + 2c₁ (where d = T(1), c₁ = merge constant)

We need: T(2) ≤ c × 2 × log(2) = 2c Choose c ≥ d + c₁, so 2c ≥ 2d + 2c₁ = T(2). ✓

Inductive step: Assume T(k) ≤ ck log k for all k < n. We must show T(n) ≤ cn log n.

T(n) = 2T(n/2) + c₁n ≤ 2 × c(n/2)log(n/2) + c₁n [by inductive hypothesis] = cn × log(n/2) + c₁n = cn × (log n - log 2) + c₁n = cn × (log n - 1) + c₁n = cn log n - cn + c₁n = cn log n - n(c - c₁) ≤ cn log n [if c ≥ c₁]

Thus, T(n) ≤ cn log n for c = max(c₁, d + c₁). ∎

The Master Theorem provides a direct formula for solving recurrences of a specific form—which conveniently includes Merge Sort's recurrence.

The Master Theorem:

For recurrences of the form T(n) = aT(n/b) + f(n) where a ≥ 1, b > 1:

Let c_crit = log_b(a). Then:

Case 1: If f(n) = O(n^c) where c < c_crit, then T(n) = Θ(n^c_crit)

Case 2: If f(n) = Θ(n^c_crit × log^k n) for k ≥ 0, then T(n) = Θ(n^c_crit × log^(k+1) n)

Case 3: If f(n) = Ω(n^c) where c > c_crit, and af(n/b) ≤ kf(n) for some k < 1, then T(n) = Θ(f(n))

Applying to Merge Sort:

Merge Sort recurrence: T(n) = 2T(n/2) + cn

Identify parameters:

• a = 2 (number of subproblems)
• b = 2 (factor by which size decreases)
• f(n) = cn (work outside recursive calls)

Calculate c_crit:

• c_crit = log_b(a) = log₂(2) = 1

Compare f(n) to n^c_crit:

• f(n) = cn = Θ(n^1) = Θ(n^c_crit)
• This is Case 2 with k = 0!

Apply Case 2:

• T(n) = Θ(n^c_crit × log^(k+1) n) = Θ(n^1 × log^1 n) = Θ(n log n)

The Master Theorem gives us O(n log n) immediately—no induction required!

A remarkable property of Merge Sort is that its best, average, and worst cases are all O(n log n). This uniformity is unusual among sorting algorithms and is one of Merge Sort's defining characteristics.

Why doesn't input order matter?

Merge Sort's behavior is data-oblivious—it always:

1. Divides the array at the midpoint (regardless of values)
2. Recursively processes both halves (regardless of values)
3. Performs a merge that scans all elements (regardless of values)

The only variation is in the number of comparisons during merging:

• Best case for merge: min(n₁, n₂) comparisons (one side exhausted quickly)
• Worst case for merge: n₁ + n₂ - 1 comparisons (perfect interleaving)

But both are O(n), so the overall complexity remains O(n log n).

Contrast with other algorithms:

Merge Sort's O(n log n) performance isn't just efficient—it's optimal for comparison-based sorting algorithms. This profound result tells us that no comparison-based algorithm can be asymptotically faster than Merge Sort.

The lower bound theorem:

Any comparison-based sorting algorithm must make at least Ω(n log n) comparisons in the worst case.

Proof sketch:

1. Information-theoretic argument: There are n! possible permutations of n elements. The algorithm must distinguish between all n! possibilities to sort correctly.

2. Decision tree model: Model the algorithm as a binary decision tree where:

   • Each internal node is a comparison (element i vs element j?)
   • Each leaf is a final sorted order
   • The tree must have at least n! leaves (one per permutation)

3. Tree height constraint: A binary tree with n! leaves has height at least log₂(n!).

4. Stirling's approximation: log₂(n!) ≈ n log₂(n) - n log₂(e) ≈ n log₂(n) - 1.44n = Θ(n log n)

5. Conclusion: The tree height (worst-case comparisons) is Ω(n log n).

Therefore, any comparison-based sorting algorithm is Ω(n log n) in the worst case. ∎

For practical analysis and competitive programming, it's useful to know the exact number of comparisons and other operations Merge Sort performs.

Comparison counts:

Let C(n) be the number of comparisons for sorting n elements.

For the recurrence C(n) = C(n/2) + C(n/2) + comparisons_in_merge:

• Best case for merge: min(n/2, n/2) = n/2 comparisons
• Worst case for merge: n/2 + n/2 - 1 = n - 1 comparisons

Best case recurrence: C_best(n) = 2C_best(n/2) + n/2

• Solution: C_best(n) = (n/2) × log₂(n) = (n log n) / 2

Worst case recurrence: C_worst(n) = 2C_worst(n/2) + n - 1

• Solution: C_worst(n) = n log₂(n) - n + 1 ≈ n log n - n

Average case (random data):

• C_avg(n) ≈ n log₂(n) - 1.2645n (derived through careful analysis)

Other operation counts:

• Array accesses: Approximately 6n log₂(n) (copies plus reads during merge)
• Recursive calls: 2n - 1 total calls (n leaves + n-1 internal nodes)
• Merge operations: n - 1 total merges
• Total elements processed: n × log₂(n) (each element participates in log n merges)

We've rigorously analyzed Merge Sort's time complexity using multiple techniques. Let's consolidate the key insights:

What's next:

With time complexity thoroughly understood, the final page of this module examines Merge Sort's space complexity. We'll analyze the O(n) auxiliary space requirement, explore trade-offs with in-place variants, and understand why the space cost is often acceptable in practice.