Watch merge sort split the array in half, then merge sorted runs back together. Guaranteed O(n log n) in every case — at the cost of O(n) extra memory.
Algorithm
Array
Comparisons
0
Swaps/writes
0
Step
0/535
Reads
0
Aux memory
0
Call depth
1/1
Slow the speed and use Step to match the pseudocode highlight with the bar colors.
Pseudocode
mergeSort(lo, hi)
mid ← (lo+hi)/2
mergeSort(lo,mid) mergeSort(mid+1,hi)
while left & right remain
a[k] ← smaller of the two fronts
copy merged run back
Time complexity
| Best | O(n log n) |
|---|---|
| Average | O(n log n) |
| Worst | O(n log n) |
| Space | O(n) |
| Stable | Yes |
Merge sort is the classic divide-and-conquer sort: split the array in half recursively down to single elements, then merge pairs by repeatedly taking the smaller front value.
Split depth is log n and each merge level touches all n elements, so O(n log n) holds for best, average, AND worst case — a guarantee quicksort cannot make. It is stable, but needs O(n) temporary space. Sorting Visualizer