Merge Sort and the Master Theorem

Merge sort is the canonical divide-and-conquer algorithm. Split the array in half, sort each half, merge.

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    return merge(left, right)

def merge(left, right):
    out = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])
    out.extend(right[j:])
    return out

Why O(n log n)?

Each call splits the work in two and does linear work for the merge. The recurrence is:

T(n) = 2 · T(n/2) + Θ(n)

Apply the master theorem with a=2, b=2, f(n)=n. Compare f(n) to n^(log_b a) = n^1. They're the same up to a constant, so we land in case 2: T(n) = Θ(n log n).

What merge sort gives you that quicksort doesn't

• Stable. Equal elements keep their relative order. That matters when you sort by one key and want the prior key's order preserved.
• Worst-case O(n log n). Quicksort is O(n²) on adversarial inputs.
• Linear-time merge is the foundation of external sorting — sorting data too big for memory, in chunks, on disk.

What it costs

• O(n) extra memory for the merge buffer. Quicksort sorts in place.
• Cache unfriendly compared to quicksort because it doesn't operate on contiguous slices.

In practice: Python's list.sort and sorted use Timsort, which is a hybrid that exploits already-sorted runs in real-world data. Pure merge sort is mostly a teaching tool now — but the divide-and-conquer pattern it teaches is everywhere.