Merge sort

O(n log n)

Merge sort is a divide-and-conquer algorithm: it halves the array down to single elements, then merges neighbouring runs back together in order. Merging is the heart of it — two already-sorted runs are woven into one in linear time. It guarantees O(n log n) in every case and is stable, at the cost of extra memory for the merge.

Array
Edit the input and press Play

How it works

  1. Split the array into two halves and sort each half the same way (recursion).
  2. Merge the two sorted halves: repeatedly take the smaller front element.
  3. Write the merged, ordered run back over the original range.
  4. Work back up until the whole array is one sorted run.

Pseudocode

1mergeSort(a, lo, hi):               # O(n log n)2  if lo ≥ hi: return3  mid ← (lo + hi) / 24  mergeSort(a, lo, mid)5  mergeSort(a, mid+1, hi)6  merge(a, lo, mid, hi)             # weave two sorted halves