ZERO / HERO
Two sorted lines zipped together

Merge Sort

The analogy

Split the line in half, and again, until every group is one kid — a group of one is already sorted. Then zip pairs of sorted groups back together by repeatedly taking the shorter kid from the front of either group. Splitting is free; the zipping does the work.

Visualizer

Watch it split and zip

step 1 / 47
5
3
8
1
9
2
7
4

8 numbers, out of order. Press play — or step through one comparison at a time.

def merge_sort(a):
    if len(a) < 2:
        return a
    mid = len(a) // 2
    return merge(merge_sort(a[:mid]),
                 merge_sort(a[mid:]))

def merge(x, y):
    out = []
    while x and y:
        out.append(x.pop(0) if x[0] <= y[0] else y.pop(0))
    return out + x + y
Check yourself

Merge sort's worst case is…