All algorithms

Merge Sort

Divide-and-conquer sort: recursively split the array in half, sort each half, then merge the two sorted halves back together in linear time.

time O(n log n)
space O(n)

Press Tab out of the box or click Resetto regenerate frames from the current input.

Visualization
No frames yet — edit input and click Run.
—
Pseudocode
mergeSort(a, lo, hi):
  if lo >= hi: return
  mid = (lo + hi) / 2
  mergeSort(a, lo, mid)
  mergeSort(a, mid+1, hi)
  merge(a, lo, mid, hi)