Mergesort (top-down)

Cost and properties

time	Θ(n log n), guaranteed
compares	≤ n lg n
space	n — not in place
stable	yes

Reference: Sedgewick & Wayne, §2.2; von Neumann 1945.

Mergesort (top-down) in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

def sort(a):
    aux = list(a)                         # ONE auxiliary array, allocated once
    _sort(a, aux, 0, len(a) - 1)
    return a

def _sort(a, aux, lo, hi):
    if hi <= lo:                          # 0 or 1 keys: already sorted
        return
    mid = lo + (hi - lo) // 2
    _sort(a, aux, lo, mid)                # sort the left half
    _sort(a, aux, mid + 1, hi)            # sort the right half
    merge(a, aux, lo, mid, hi)            # merge two sorted halves

def merge(a, aux, lo, mid, hi):
    aux[lo:hi + 1] = a[lo:hi + 1]         # copy out, then merge back in
    i, j = lo, mid + 1
    for k in range(lo, hi + 1):
        if i > mid:                       # left half is used up
            a[k] = aux[j]; j += 1
        elif j > hi:                      # right half is used up
            a[k] = aux[i]; i += 1
        elif aux[j] < aux[i]:             # strictly less: keeps it STABLE
            a[k] = aux[j]; j += 1
        else:
            a[k] = aux[i]; i += 1

Why it works

Why n log n falls out

The recursion halves the array until the pieces are single keys — that is lg n levels — and each level merges a total of n keys in linear time. n per level × lg n levels = ~n lg n, on every input, with no probabilistic caveat. Mergesort is asymptotically optimal: no compare-based sort can beat n lg n.

The merge is the algorithm

Copy the range into aux, then walk two indices and always take the smaller front key. The four branches are exhaustive: left exhausted, right exhausted, right strictly smaller, otherwise left. Getting the boundary cases right is the whole difficulty — and note there is one auxiliary array, created once in sort. Allocating inside merge is the classic performance bug: it turns a linear merge into a memory-allocation storm.

Stability, in one character

aux[j] < aux[i] is strict, so when keys are equal the left half wins and equal keys keep their original relative order. Change it to <= and mergesort is no longer stable. Stability is why mergesort is the sort of choice when records are sorted by one field after another.

Practical improvements the course adds

• Cutoff to insertion sort for ranges of ~7 keys: recursion overhead dominates for tiny arrays (20–30% faster overall).
• Skip the merge when a[mid] <= a[mid+1] — the range is already sorted. Makes nearly-ordered input linear.
• Alternate the roles of a and aux to avoid the copy entirely.

What to try in the animation

Every input costs the same ~n lg n. Try already sorted — mergesort cannot exploit it (bottom-up with a sorted-check can).

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

• random — 7 10 5 3 8 4 2 9 6 1
• MERGESORTEXAMPLE — M E R G E S O R T E X A M P L E
• already sorted — 1 2 3 4 5 6 7 8 9 10
• reverse sorted — 10 9 8 7 6 5 4 3 2 1
• all equal — 5 5 5 5 5 5 5 5
• few distinct — 2 1 3 1 2 3 1 2 3 1

Open Mergesort (top-down) in the player →

The rest of Mergesort

• Bottom-up mergesort Merge every adjacent pair, then every pair of pairs, doubling the width each pass.