merge-sort

Halve the array, sort each run, merge them back.

best: O(n log n)
average: O(n log n)
worst: O(n log n)
space: O(n)

reference implementation

verified source·read-only

loading editor

brief

Merge sort splits the array in half, sorts each half recursively, then merges the two sorted runs by repeatedly taking the smaller front element. Every level of the recursion does linear work, so the running time is O(n log n) in the worst case — the divide-and-conquer contract that quicksort only delivers on average.

the math

Two sorted runs

By the time a merge runs, both halves are already sorted — that is the recursion's contract.
The merge only has to compare the two front elements and take the smaller one.
When one run empties, the rest of the other run is appended unchanged.

Writing the merged run

The merge builds the combined run in a buffer, then writes it back into the array in order.
Each element is written exactly once per merge, into a buffer that never holds more than $n$ elements - hence the $O(n)$ auxiliary space.
The bars you see move are these writes, not swaps.

Why O(n log n)

Halving the array ends after $\lceil \log_2 n \rceil$ levels.
Each level merges runs that together cover all $n$ elements, so a level costs $O(n)$ comparisons and writes.
Total: $n \cdot \lceil \log_2 n \rceil = O(n \log n)$ , guaranteed — no bad input changes the shape.

Stability

When the two front keys are equal, the merge takes from the left run first ( $\le 0$ ).
Equal elements therefore keep their original relative order: merge sort is stable.
The final green marks are applied only once the whole array is merged.

▍ Merge Sort · small

requesting trace

· decoding trace

· replaying events

· mounting renderer

0/0

fun facts

John von Neumann invented merge sort in 1945; Goldstine and von Neumann published a detailed analysis in 1948.
It is one of the first divide-and-conquer algorithms, and the O(n log n) bound holds for every input — there is no bad case.
Taking from the left run when keys tie is what makes it stable: equal elements keep their original order.
External merge sort, its disk-based cousin, is how databases and text indexes sort more data than fits in memory.

merge-sortstep 0/00%spaceplay←→steppprojectorrreset