Merge Sort — Divide, Conquer, Stable Combine

Merge sort splits the array in half, sorts each half recursively, and merges two sorted halves in linear time. It is the canonical stable O(n log n) comparison sort with predictable performance.

Why this shows up in the real world

Python’s sorted and list.sort use Timsort, a hybrid built on merge sort’s stability for real-world data with runs. External sorting of files larger than RAM merges sorted chunks from disk—merge sort’s structure maps directly. Parallel databases exploit the same divide pattern to sort partitions concurrently then merge.

Core idea (explained for students)

Recurrence T(n) = 2T(n/2) + O(n) solves to O(n log n). Merge step uses two pointers; extra O(n) space for a temporary buffer is typical in array implementations. Stability comes from choosing left element on ties when merging. Bottom-up merge sort avoids recursion overhead and is cache-friendly in some implementations.

Try this in Python

def merge_sort(a: list[int]) -> list[int]:
    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
    return out + left[i:] + right[j:]


print(merge_sort([3, 1, 4, 1, 5, 9, 2, 6]))

Common mistakes

• Slice copies doubling memory—use indices instead.
• Off-by-one mid calculation (lo+hi)//2 vs len//2 patterns.
• Merging without sentinel nodes—careful pointer end conditions.

Key takeaways

• Stable and predictable O(n log n).
• Extra linear space is the trade-off vs in-place quicksort.
• Understand merge to master inversion count and k-way ideas.