Merge Sort Explained

The algorithm has two phases. Divide: recursively split the array until each piece has a single element (which is trivially sorted). Conquer: repeatedly merge pairs of sorted pieces by walking two pointers and always taking the smaller front element, until one fully sorted array remains.

mergeSort(a):
  if length(a) <= 1: return a
  mid = length(a) / 2
  left = mergeSort(a[0..mid])
  right = mergeSort(a[mid..end])
  return merge(left, right)

merge(L, R):
  result = []
  while L and R not empty:
    if L[0] <= R[0]: result.push(L.shift())
    else: result.push(R.shift())
  return result + L + R

Merge Sort is O(n log n) in best, average, and worst case — the log n comes from halving the array, the n from each merge level touching every element. It needs O(n) auxiliary space for the merge buffer, so it is not in-place. It is stable, which is why Java uses it (as Tim Sort) for sorting objects.

Because Merge Sort accesses data sequentially and merges streams, it is the standard approach for external sorting — sorting files too large to fit in RAM. Choose Merge Sort when you need guaranteed O(n log n), stability, or are sorting linked lists. Compare it with Quick Sort in our popular head-to-head.