What is merge sort (Merge Sort)?

AlgorithmsJunior~3 min read

What is merge sort (Merge Sort)?

Short answer

Merge sort is a stable "divide and conquer" algorithm: it recursively splits the array in half, sorts the parts, and merges them into one sorted array. It guarantees O(n log n) time in all cases, requires O(n) extra memory, and delivers predictable, uniform performance.

Detailed breakdown

Algorithm idea (divide and conquer)

Split: recursively divide the array into two halves, down to subarrays of length 0 or 1.
Sort the subarrays: each subarray is sorted using the same method.
Merge: two already sorted subarrays are combined into one sorted array by comparing one element from each side (two pointers).
Base case: an array of length 0 or 1 is already sorted.

Complexity and key properties

Time: O(n log n) in the best, average, and worst cases.
Memory: O(n) extra memory for arrays (classic implementation).
Stability: yes (preserves the relative order of equal elements with a correct merge operation).
Determinism: the same asymptotics for any input, with no degradation like QuickSort.
Good for linked lists: can work with O(1) extra memory, since only pointer rearrangement is needed.
Suitable for external sorting: works efficiently with files/streams (limited RAM).
Parallelization: easy to parallelize at the stage of recursively sorting the halves.

Property	Value
Best/average/worst time cases	O(n log n)
Extra memory (array)	O(n)
Stability	Yes (with a <= comparison in the merge)
Adaptivity to nearly sorted data	No (classic version)

When to use it and when not to

Use it: when stability and predictable O(n log n) worst-case performance matter (for example, sorting by several keys).
Use it: when working with lists and for external sorting of large data that does not fit in memory.
Be careful: on arrays it requires O(n) memory; if memory is limited, consider HeapSort (in-place, but unstable) or QuickSort (faster average case, but worst case O(n^2)).

Recursive implementation (top-down, JS)

javascript

// Stable merge sort (top-down)
function mergeSort(arr) {
  if (arr.length <= 1) return arr.slice(); // copy, so the original array is not mutated
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  const res = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    // '<=' keeps the sort stable: elements from left go first when equal
    if (left[i] <= right[j]) {
      res.push(left[i++]);
    } else {
      res.push(right[j++]);
    }
  }
  while (i < left.length) res.push(left[i++]);
  while (j < right.length) res.push(right[j++]);
  return res;
}

// Example
const arr = [5, 2, 4, 6, 1, 3, 2];
console.log(mergeSort(arr)); // [1, 2, 2, 3, 4, 5, 6]

Iterative (bottom-up) implementation (JS)

The bottom-up version avoids recursion: first it merges blocks of size 1, then 2, 4, 8, and so on.

javascript

function mergeSortBottomUp(a) {
  const n = a.length;
  const aux = new Array(n);
  for (let sz = 1; sz < n; sz <<= 1) {
    for (let lo = 0; lo < n - sz; lo += sz << 1) {
      const mid = lo + sz;
      const hi = Math.min(lo + (sz << 1), n);
      mergeRange(a, aux, lo, mid, hi);
    }
  }
  return a;
}

function mergeRange(a, aux, lo, mid, hi) {
  // Copy into the buffer
  for (let t = lo; t < hi; t++) aux[t] = a[t];
  let i = lo, j = mid, k = lo;
  while (i < mid && j < hi) {
    if (aux[i] <= aux[j]) a[k++] = aux[i++];
    else a[k++] = aux[j++];
  }
  while (i < mid) a[k++] = aux[i++];
  while (j < hi) a[k++] = aux[j++];
}

// Example
const arr2 = [7, 1, 4, 9, 0, 3, 8, 2, 6, 5];
console.log(mergeSortBottomUp(arr2));

Memory allocation optimization: a single buffer

To avoid creating temporary arrays at every step of the recursion, pass a single shared auxiliary buffer.

javascript

function mergeSortWithBuffer(a) {
  const aux = new Array(a.length);
  sort(a, aux, 0, a.length);
  return a;
}

function sort(a, aux, lo, hi) {
  if (hi - lo <= 1) return;
  const mid = lo + ((hi - lo) >> 1);
  sort(a, aux, lo, mid);
  sort(a, aux, mid, hi);
  mergeRanges(a, aux, lo, mid, hi);
}

function mergeRanges(a, aux, lo, mid, hi) {
  for (let t = lo; t < hi; t++) aux[t] = a[t];
  let i = lo, j = mid, k = lo;
  while (i < mid && j < hi) {
    if (aux[i] <= aux[j]) a[k++] = aux[i++];
    else a[k++] = aux[j++];
  }
  while (i < mid) a[k++] = aux[i++];
  while (j < hi) a[k++] = aux[j++];
}

Merge-sorting a linked list (in brief)

Splitting the list into two halves is done using slow/fast pointers.
Merging is a rearrangement of the next links; extra memory is O(1), and the algorithm remains stable.

Typical interview questions and key answers

Why O(n log n)? There are log n levels of splitting, and at each level we process n elements in total during merging: n × log n.
What is stability? Equal elements keep their original order. In merge, check the condition using '<='.
Why isn't it in-place? Classic merging requires a temporary buffer; complex in-place variants exist, but they are rarely used because of their complexity and constants.
Comparison with QuickSort: MergeSort is stable and guarantees O(n log n) in the worst case, but requires O(n) memory; QuickSort is usually faster in practice and in-place, but its worst case is O(n^2) without randomization/median-of-three.
Can it be parallelized? Yes: sort the left and right halves on different threads/workers, then perform a sequential merge.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.