Merge Sort

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

Size48
ComparingSwap/writePivot/keyReadSorted
Speed50×

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

BestO(n log n)
AverageO(n log n)
WorstO(n log n)
SpaceO(n)
StableYes

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

Frequently asked questions

Merge sort vs quicksort?
Merge guarantees O(n log n) and is stable; quicksort is usually faster in practice (cache-friendly, smaller constants) but can degrade to O(n²).
Why does merge sort need extra memory?
Merging in place would overwrite values not yet read, so a temporary buffer of size O(n) holds the merged output.

Other algorithms