Sorting II — Merge Sort

Merge sort is the first fast sorting algorithm most people learn. It runs in O(n log n) time — fast enough for real work — and it shows off a powerful idea: divide and conquer. Split the list in half, sort each half, then merge the two sorted halves back together. The merge is the clever part, and it is what the animation focuses on.

The idea

Sorting a big list is hard. Sorting a list of one item is free — it is already sorted. Merge sort uses that: it keeps splitting until every piece is a single element, then merges pieces back together two at a time, always keeping them sorted.

The merge works because both halves are already sorted. The smallest value in the whole thing must be at the front of one half or the other — so you only ever compare two values at a time to find the next smallest.

Walk through it

Press Play on the right, or step with Next / Back. The two halves are [2, 4, 5] and [1, 3, 6]. Watch what the merge does:

• Pointer i sits on the front of the left half, j on the front of the right half, k on the next empty result slot.
• Each step compares the two fronts (they turn blue). The smaller one is written into the result row and turns green.
• That pointer steps forward; the value it just used turns grey (consumed).
• When one half runs out, the rest of the other half is already sorted, so it copies straight across.

Notice we never look backwards. Every element is touched once, so the whole merge is just one linear pass.

The code, line by line

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    res, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            res.append(left[i])
            i += 1
        else:
            res.append(right[j])
            j += 1
    res += left[i:]
    res += right[j:]
    return res

• Lines 2–3 are the base case: a list of zero or one item is already sorted, so return it.
• Lines 4–6 divide: split at the middle and recursively sort each half. This is where the log n comes from — the list halves each time.
• Lines 8–14 are the merge, the part you see animated. While both halves still have items, compare their fronts and append the smaller one, then advance that pointer.
• Lines 15–16 drain the leftovers. When one half empties, the other half's remaining items are already sorted, so they tack on directly.
• Using <= (not <) on line 9 keeps the sort stable: equal values keep their original order.

Complexity

Why O(n log n)? Splitting in half each time gives about log n levels. At every level you merge, and each merge together touches all n elements once — so n work per level times log n levels = n log n. The space is O(n) because each merge builds a new result list the size of the inputs; unlike bubble sort, merge sort is not in place.

When to use / pitfalls

Practice