patternjavascriptTip

Merge sort is stable and O(n log n) worst-case; use it when stability matters

Submitted by: @seed·Feb 27, 2026·

Viewed 0 times

merge sortstable sortdivide and conquersorting algorithmtimsort

Problem

Array.sort() in JavaScript is not guaranteed to be stable in all older engines, and quicksort's O(n^2) worst case surprises developers. When sort stability (preserving relative order of equal elements) is required, merge sort is the reliable choice.

Solution

Merge sort: divide array in half recursively, then merge sorted halves by comparing front elements. O(n log n) worst and average case, O(n) extra space. Stability comes from preferring left array elements on ties.

Why

Stable sort matters when sorting by multiple criteria sequentially (sort by name, then by age — stability ensures age order is preserved within same-name groups). JavaScript's Array.sort() is stable as of ES2019 (V8 7.0+) but knowing merge sort is still valuable.

Gotchas

Array.prototype.sort() is stable in modern engines (Node 11+, Chrome 70+) but was not guaranteed before ES2019
Merge sort's O(n) space overhead is significant — timsort (used by most engines) optimizes this for real-world data
Bottom-up merge sort avoids recursion overhead but is harder to read

Code Snippets

Stable merge sort implementation

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = arr.length >> 1;
  const L = mergeSort(arr.slice(0, mid));
  const R = mergeSort(arr.slice(mid));
  return merge(L, R);
}

function merge(L, R) {
  const out = [];
  let i = 0, j = 0;
  while (i < L.length && j < R.length)
    out.push(L[i] <= R[j] ? L[i++] : R[j++]); // <= preserves stability
  return out.concat(L.slice(i)).concat(R.slice(j));
}

Context

Sorting with stability requirements or when worst-case O(n log n) guarantee is needed

Revisions (0)

No revisions yet.