Merge Sort Visualization

Merge Sort splits the list in half, sorts both halves, then merges the two sorted halves into one.

How it works

Merge Sort keeps splitting the list until every piece has one element, which is sorted by definition. Then it merges neighbouring pieces: it repeatedly takes the smaller front value of two sorted runs, so two sorted runs become one longer sorted run. Doubling the run length each pass means about log n passes of n work each.

That gives n log n comparisons in the best, average and worst case, which is why Merge Sort is the dependable choice when worst-case time matters. It is stable, so equal values keep their order, and it is the basis of most library sorts for linked lists and external (on-disk) sorting. The cost is extra memory for the merge buffer.

What to watch for

Watch small sorted rainbows appear side by side, then pairs of them fuse into longer and longer sorted runs until one run covers everything.

Complexity

Best

n log n

Average

n log n

Worst

n log n

Extra space

n

Stable

Yes

Race it

Same shuffle, same speed, one winner: Merge vs Quick. Or open the studio to try other layouts, sizes and speeds, and make a video of it.

FAQ