Merge sort visualizer

Type a list in the box, separated by commas, spaces or new lines. Numbers are sorted by value and words alphabetically. The animation below plays the sort: the part of the list being worked on stays bright and the rest fades back, yellow bars are being compared, and orange marks the item that has just been placed.

Play, Step forward, Step back and Speed work as you'd expect. Show the steps lists every split and every merge in order. The animation takes up to 24 items.

Merge sort splits the list in half, then splits each half in half again, until every piece is a single item. A single item is already sorted.

Then it merges the pieces back together in pairs. Merging two sorted lists is easy: look at the first item of each, take the smaller one, and repeat. When one list runs out, the rest of the other follows on. Pair by pair, the sorted pieces grow until there's one sorted list.

Halving the list again and again takes about log₂ n rounds, and each round of merging looks at every item once. So merge sort makes on the order of n × log₂ n comparisons, written O(n log n). For a thousand items that's around 10,000 comparisons, where bubble sort can need nearly 500,000.

Merge sort is also stable: items that compare equal stay in the order they started in, which matters when sorting a table by one column after another.

Merge sort was invented by John von Neumann in 1945. A detailed description of the bottom-up version, which merges pairs, then fours, then eights, appeared in a report by Goldstine and von Neumann in 1948.