Interactive demo
Merge Sort Visualization
Merge sort divides an array into halves until only single elements remain and then merges the sorted halves back together. It is stable and always needs O(n log n) steps, but it needs an auxiliary array.
Press “Next Step” to advance one step at a time, or “Play” to run the algorithm on its own.
Playback
Legend
- Unsorted element
- Head of the left run
- Head of the right run
- In the auxiliary array
- Sorted run
Runtime and properties
Best case
O(n log n)
Even sorted input is divided and merged completely: log n levels of n steps.
Average case
O(n log n)
log n levels of halving, and every level merges all n elements.
Worst case
O(n log n)
Halving never depends on the values, so the split is always balanced.
Extra memory
O(n)
Merging needs an auxiliary array as large as the section being merged.
Stable
Yes
On ties the element from the left run is taken first.
In-place
No
The auxiliary array doubles the memory needed.
n is the number of elements. O(n log n) is the best a sorting algorithm based on comparisons can achieve.
Compared with the other sorting algorithms
1. Divide
The section is split in the middle again and again until every part holds a single element, which is sorted by definition.
2. Merge
Two sorted runs are merged by comparing their first elements and moving the smaller one into the auxiliary array. On ties the left element goes first, which keeps the sort stable.
3. Copy back
The merged run is copied back into the array. Level by level the sorted runs grow until the whole array is one sorted run.