Merge Sort

Divide-and-conquer sorting that recursively splits and merges sorted subarrays.

O(n log n)SortingDivide & Conquer

Phase 1f(x)

The Mathematics

Divide-and-conquer paradigm, recurrence, and proof of correctness

Divide-and-Conquer Paradigm

Merge Sort breaks the problem into three steps:

Divide: Split the array $A[0..n-1]$ into two halves at the midpoint $\lfloor n/2 \rfloor$ .

Conquer: Recursively sort each half.

Combine: Merge the two sorted halves into a single sorted array.

\text{MergeSort}(A) = \text{Merge}\bigl(\text{MergeSort}(A_L),\; \text{MergeSort}(A_R)\bigr)

Recurrence Relation

Each recursive call processes half the array. The merge step takes $O(n)$ to combine two sorted halves:

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

Applying the Master Theorem (case 2: $a=2, b=2, f(n)=O(n)$ , so $\log_b a = 1$ and $f(n) = \Theta(n^{\log_b a})$ ):

T(n) = O(n \log n)

The Merge Operation

Given two sorted sequences $L$ and $R$ , the merge produces a sorted union by repeatedly taking the smaller head element:

\text{Merge}(L, R): \text{while } L \neq \emptyset \text{ and } R \neq \emptyset, \text{ take } \min(\text{head}(L), \text{head}(R))

Each element is compared at most once, so the merge takes $O(|L| + |R|) = O(n)$ time.

Correctness (by Induction)

Base case: An array of size $\leq 1$ is trivially sorted.

Inductive step: Assume $\text{MergeSort}$ correctly sorts arrays of size $< n$ . Then for size $n$ :

$\bullet$ Both halves are correctly sorted (by inductive hypothesis)

$\bullet$ $\text{Merge}$ correctly combines two sorted sequences

$\bullet$ Therefore the result is sorted $\blacksquare$

Phase 2▶

See It Work

Sorting [38, 27, 43, 3, 9, 82, 10] via recursive splitting and merging

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

Depth 0

Step 1 of 14

Start with the unsorted array. We will recursively divide it in half.

Phase 3</>

The Code

Mapping divide-and-conquer to recursive Python

Mathematical Formulation

|A| \leq 1 \Rightarrow \text{return } A

Base case: a single element is already sorted

\text{mid} = \lfloor n/2 \rfloor

Divide the array at the midpoint

T(n/2) + T(n/2)

Two recursive calls, each on half the array

\text{Merge}(L, R) : O(n)

Merge step: combine two sorted halves in linear time

L[i] \leq R[j] \Rightarrow \text{take } L[i]

Compare heads of both halves, take the smaller

\text{Total: } T(n) = O(n \log n)

Master theorem gives O(n log n) total

Python Implementation

def merge_sort(A):
    if len(A) <= 1:                  # Base case
        return A
    mid = len(A) // 2               # Divide
    left = merge_sort(A[:mid])      # Recurse left
    right = merge_sort(A[mid:])     # Recurse right
    return merge(left, right)       # Conquer

def merge(L, R):
    result = []
    i = j = 0
    while i < len(L) and j < len(R):  # Compare heads
        if L[i] <= R[j]:
            result.append(L[i])        # Take from left
            i += 1
        else:
            result.append(R[j])        # Take from right
            j += 1
    result.extend(L[i:])               # Remaining left
    result.extend(R[j:])               # Remaining right
    return result