Merge Sort: Divide, Conquer, Combine

"Merge sort's whole idea fits in one sentence: a problem you can't easily solve, you split in half, solve each half, and stitch the answers together. That 'split, solve, combine' rhythm is divide-and-conquer, and it reaches far beyond sorting."

The Three Steps

Merge sort is the cleanest example of divide and conquer:

Divide: split the array into two halves.
Conquer: recursively sort each half (the recursion bottoms out at single elements, which are trivially sorted).
Combine: merge the two sorted halves into one sorted whole.

The clever part is the merge: given two already-sorted halves, walk a pointer down each, repeatedly taking the smaller of the two fronts. Because both halves are sorted, this produces a fully sorted result in a single O(n) pass — the two-pointer technique from the Arrays track, doing the real work.

Why It's Guaranteed O(n log n)

Count the work by levels. Halving repeatedly gives log n levels of recursion (n → n/2 → n/4 → … → 1). At each level, the merges across all the pieces together touch all n elements once — O(n) per level. So total work is n × log n = O(n log n). And crucially, this holds regardless of the input — unlike quicksort, merge sort has no bad-pivot worst case; it's O(n log n) on sorted data, reverse data, random data, always. That guarantee is its calling card.

Merge sort: divide in half, sort each half recursively, merge the sorted halves in O(n) via two pointers. log n levels × O(n) per level = guaranteed O(n log n), every input. It's stable but uses O(n) extra space for merging.

Its Strengths and Its Cost

Merge sort has two standout virtues. It's stable — equal elements keep their original relative order, which matters when you sort by one key after another (sort by name, then stably by date, and same-date entries stay name-ordered). And it parallelizes and externalizes beautifully: it's the basis of external sorting (sorting data far too big for memory, by merging sorted chunks from disk) and it sorts linked lists well (no random access needed, unlike quicksort). The cost is O(n) extra space for the merge buffer — that's the trade against quicksort's in-place partitioning, which the next lesson covers.

Pippa's Confession

The merge step confused me until Dad framed it as two sorted lines of people merging into one: you just keep taking whoever's shorter at the front of the two lines. Obvious, once seen. What stayed with me was bigger than sorting, though — 'split it, solve the pieces, combine' turned out to be a strategy, not just a sort. The next track (recursion) is really about learning to see that divide-and-conquer shape everywhere, and merge sort was where it first clicked for me.

Code

Merge sort: split, recurse, merge·python

def merge_sort(arr):
    if len(arr) <= 1:                 # base case: 0 or 1 element is sorted
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])      # divide + conquer: sort each half
    right = merge_sort(arr[mid:])
    return merge(left, right)         # combine

def merge(left, right):
    """Merge two SORTED lists into one, O(n), with two pointers."""
    result, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:       # '<=' keeps it STABLE (ties keep order)
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])           # append whatever's left over
    result.extend(right[j:])
    return result

print(merge_sort([5, 2, 8, 1, 9, 3]))   # [1, 2, 3, 5, 8, 9]
# log n levels of halving, O(n) merge per level -> O(n log n), every input.
# The two-pointer merge is the engine; the recursion just sets it up.

Exercise

Trace merge sort on [3, 1, 2]: show the recursive splits down to single elements, then the merges back up. Separately, explain why merge sort is O(n log n) on EVERY input while quicksort can degrade to O(n²) — what about merge sort's structure prevents a bad case?

Hint

[3,1,2] → [3] and [1,2] → [1],[2] merge to [1,2]; then merge [3] with [1,2] → [1,2,3]. Merge sort always splits exactly in half regardless of values, so it's always log n levels — there's no pivot choice to go wrong, hence no O(n²) worst case.

The Three Steps

Why It's Guaranteed O(n log n)

Its Strengths and Its Cost

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0