SortingSorting

Merge Sort

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

Learn Merge Sort →
29
0
10
1
14
2
37
3
13
4
5
5
42
6
21
7
1/54Start with 8 elements. Merge sort splits the array in halves until pieces of size one, then merges sorted pieces back together.
Left halfRight halfHeads being comparedMerged / sorted
PseudocodeLearn Merge Sort →
1mergeSort(a, lo, hi):
2  if lo >= hi: return
3  mid = (lo + hi) // 2
4  mergeSort(a, lo, mid)
5  mergeSort(a, mid+1, hi)
6  merge(a, lo, mid, hi):
7    i = lo, j = mid+1, buf = []
8    while i <= mid and j <= hi:
9      if a[i] <= a[j]: buf.push(a[i++]) else buf.push(a[j++])
10    append leftovers of both halves to buf
11    copy buf back into a[lo..hi]
Complexity
best O(n log n)
avg O(n log n)
worst O(n log n)
space O(n)
Speed