0

Merge Sort

Medium

Split the array in half, sort each half recursively, then merge the two sorted runs in linear time.

divide and conquerstableO(n log n)
TimeO(n log n) always
SpaceO(n)
InputComma separated numbers
38
0
27
1
43
2
3
3
9
4
82
5
10
6

Divide until every piece has one element, then merge upward.

merges0writes0
1 / 40
sort(lo, hi):
if lo >= hi: return
mid = (lo + hi) / 2
sort(lo, mid); sort(mid+1, hi)
merge(lo, mid, hi)
merge: walk both halves, always taking the smaller front
Why it matters

Stable, predictable, and the basis for counting inversions and external sorting.

Practise this
Sort ListMCount InversionsHMerge Sorted ArrayE
Keyboard
space play← → stepr restartctrl K search

More in Sorting

Quickselect
O(n) expected, O(n^2) worst
Bubble Sort
O(n^2), best O(n) when already sorted
Selection Sort
O(n^2) always
Insertion Sort
O(n^2), O(n) on nearly sorted input
Quick Sort
O(n log n) average, O(n^2) worst
Counting Sort
O(n + k)
Next visualiser
Quick Sort