Merge Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Merge Sort

Split the array in half, sort each half recursively, then merge the two sorted halves. Guaranteed O(n log n), always stable.

How it works

Merge Sort is the textbook divide-and-conquer sort. The split is trivial — you just pick the midpoint. The real work is in the merge step that fuses two sorted runs back into one.

1. Divide: split arr[lo..hi] at midpoint m.
2. Conquer: recursively sort arr[lo..m] and arr[m+1..hi].
3. Combine: merge the two sorted runs into an auxiliary buffer, then copy back.

Because the work at each level is O(n) and there are O(log n) levels, total time is O(n log n) in all cases. The merge step also preserves the original relative order of equal keys, which makes Merge Sort the canonical stable sort.

Complexity

Interactive visualization

Pseudocode

procedure mergeSort(A, lo, hi):
  if lo < hi:
    m ← (lo + hi) / 2
    mergeSort(A, lo, m)
    mergeSort(A, m + 1, hi)
    merge(A, lo, m, hi)

JavaScript implementation

function mergeSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return arr;
  const m = (lo + hi) >> 1;
  mergeSort(arr, lo, m);
  mergeSort(arr, m + 1, hi);
  merge(arr, lo, m, hi);
  return arr;
}
function merge(arr, lo, m, hi) {
  const aux = arr.slice(lo, hi + 1);
  let i = 0, j = m - lo + 1, k = lo;
  while (i <= m - lo && j <= hi - lo) {
    arr[k++] = aux[i] <= aux[j] ? aux[i++] : aux[j++];
  }
  while (i <= m - lo) arr[k++] = aux[i++];
  while (j <= hi - lo) arr[k++] = aux[j++];
}

Pros and cons

When to use it

• External sorting — chunks of disk-resident data.
• Stability-required workloads (Python, Java for objects).
• Parallel and distributed sort implementations.