Merge Sort & Divide-and-Conquer

Picture a deck of cards spread face-up on a table. If you could only ever compare two cards at a time, how would you put the whole deck in order?

Here is one neat way. Split the deck in half, sort each half, then merge the two sorted halves into one. But “sort each half” is the very same problem at half the size — so split again, and again, until every pile is a single card. A single card is already sorted. Now you walk back up: merge two one-card piles into a sorted pair, merge two sorted pairs into a sorted four, and keep merging until the whole deck is in order.

That is merge sort. And the move underneath it — break a problem into smaller copies of itself, solve those, and combine the results — is called divide and conquer, one of the most important patterns in all of computing.

The three steps, every time

Every divide-and-conquer algorithm wears the same skeleton:

1. Divide — split the input into smaller sub-problems.
2. Conquer — solve each one recursively, stopping at a base case small enough to answer directly.
3. Combine — stitch the sub-answers into the answer for the whole.

For merge sort, those steps are: split the array at its midpoint; sort the two halves recursively; treat a 0- or 1-element array as already sorted (the base case); and merge two sorted halves by repeatedly taking the smaller of the two front elements.

The merge, step by step

Merging is where the real work lives, and it is simpler than it sounds. Given two already-sorted lists, you keep one finger on the front of each and always take the smaller of the two:

left  = [3, 27, 38]      right = [1, 9, 43]

3 vs 1   → take 1    →  [1]
3 vs 9   → take 3    →  [1, 3]
27 vs 9  → take 9    →  [1, 3, 9]
27 vs 43 → take 27   →  [1, 3, 9, 27]
38 vs 43 → take 38   →  [1, 3, 9, 27, 38]
right empty → copy 43 →  [1, 3, 9, 27, 38, 43]

Merging two halves of total size k costs at most k comparisons — one O(n) sweep. That sweep, repeated at every level, is the engine of the whole algorithm.

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:      # <= keeps equal elements in order (stable)
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])          # copy whatever is left over
    result.extend(right[j:])
    return result

def merge_sort(arr):
    if len(arr) <= 1:
        return arr                   # base case: already sorted
    mid = len(arr) // 2
    return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))

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

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

Why it is O(n log n) — always

That O(n) extra space is the price of the guarantee. In-place would mean sorting with only a constant scrap of memory beyond the input; merge sort is not in-place, because the merge has to write its output into a temporary buffer — you cannot fold two sorted halves together inside the original array without losing track of what goes where.

Why stability is worth caring about

A sort is stable if elements that compare as equal come out in the same order they went in. Merge sort is stable, because the merge takes the left element first whenever two are equal (that is the <= in the code).

Why does it matter? Suppose you sort a table of students by name, then re-sort by grade. With a stable sort, students sharing a grade stay in the name order you just gave them. With an unstable sort, that earlier work is scrambled. Stability is what lets you build a multi-key order one key at a time — the subject of the Timsort lesson.

Practice