Merge sort is the textbook example of divide and conquer: break a hard problem into smaller versions of itself, solve those, then combine the results. It's one of the few sorting algorithms that guarantees O(n log n) performance no matter what the input looks like — no worst-case O(n²) surprise waiting for unlucky data.

The Core Idea

Merge sort works in two phases. First, it recursively splits the array in half until each piece contains just a single element (which is, trivially, already sorted). Then, working back up the recursion, it repeatedly merges pairs of sorted pieces into larger sorted pieces, until the whole array is one sorted sequence.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr  # base case: a single element is already "sorted"

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)


def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result


print(merge_sort([38, 27, 43, 3, 9, 82, 10]))

Output:

[3, 9, 10, 27, 38, 43, 82]

The Merge Step, Slowly

The merge() helper is where the real work happens. Given two already-sorted lists, it builds a single sorted list by repeatedly comparing the front of each list and taking the smaller one — exactly how you'd merge two sorted piles of playing cards by hand, always flipping over whichever top card is lower. Because both input lists are already sorted, this comparison-and-take process only ever needs a single linear pass through each list, which is what makes the merge step O(n) for n total elements.

Why O(n log n) Every Time

The recursion splits the array in half at every level, so there are log n levels of splitting (think: how many times can you halve n before reaching 1?). At each level, merging all the pieces back together touches every element exactly once, which costs O(n) per level. Multiply the O(log n) levels by the O(n) work per level, and you get O(n log n) — and critically, this holds regardless of the input order, since splitting in half and merging don't care whether the data was already sorted, reverse sorted, or random.

Stability and the Space Tradeoff

Merge sort is stable — the merge step takes from the left list whenever values are equal (left[i] <= right[j]), which preserves the original relative order of equal elements. The cost for merge sort's reliability is memory: the classic implementation above allocates new lists at every merge, using O(n) extra space, unlike quick sort, which can sort in place. For a complete runnable version with step-by-step tracing, see the merge sort program example.