Merge Sort

Merge sort splits the list in half again and again until every piece has one value, then merges the sorted pieces back together, always taking the smaller front value.

Start

5
3
8
2
9
1
4

Merge buffer

empty

  • Comparing
  • Just merged
  • Sorted
  • Outside this part

Merge sort splits the list in half until each piece has one value, then merges sorted pieces back together.

Step 1 / 34
Comparisons
0
Writes
0
mergeSort(lo, hi):
  if hi − lo < 1: return
  mid = (lo + hi) / 2
  mergeSort(lo, mid); mergeSort(mid + 1, hi)
  merge: take the smaller front value of each half
  copy the merged values back into lo..hi

What's happening?

  1. Split the range at the middle and sort each half (by the same method).
  2. A piece with one value is already sorted — that is where the splitting stops.
  3. Merge two sorted halves by repeatedly taking the smaller of their front values into a buffer, then copy the buffer back.

Complexity

Time
O(n log n) always — best, average and worst
Space
O(n) for the merge buffer

Where you'll meet it

Sorting linked lists, external sorting of files too big for memory, and the basis of TimSort (Python, Java objects). Its guaranteed O(n log n) and stability matter.

Common mistake

Forgetting the extra memory. Merge sort needs a buffer as big as the list, unlike quick sort or heap sort.

FAQ

Why is merge sort O(n log n)?

Halving gives about log n levels, and each level merges all n values once.

Is merge sort stable?

Yes, as long as the merge takes from the left half when values are equal — as it does here.

Merge sort vs quick sort?

Merge sort is predictable and stable but needs extra memory; quick sort is usually faster in practice and sorts in place.