Solution

You'll implement merge sort: split an array in half, recursively sort each half, then merge the two sorted halves back together into one sorted array.

The problem, in plain English

You have a stack of unsorted papers. One way to sort them: split the stack in half, hand each half to a colleague, and ask each of them to sort their half however they like. When both halves come back, you have two sorted piles — and merging two sorted piles into one sorted pile is easy. Walk the top of each pile in parallel, always taking whichever top card is smaller. That's merge sort. The "ask a colleague" step is the recursive call; the merge step is where the actual ordering work happens.

The mental model

Merge sort has two phases that line up with the call stack. On the way down, you keep cutting the array in half until you reach arrays of length one — those are trivially sorted (a single element is in order with itself). On the way back up, you merge pairs of sorted children into sorted parents, ending with the whole array sorted at the root. The picture looks like a binary tree: splits going down, merges going up.

The merge step is where ordering actually happens. Given two already-sorted arrays, you hold a pointer at the front of each, compare the two front elements, push the smaller one into your output, advance that pointer, and repeat. When one side empties, drain the other. That's the entire algorithm — the recursion is just bookkeeping that keeps handing the merge two sorted inputs.

A first attempt

Before reaching for recursion, you might try something simpler — a basic bubble sort, which everyone learns first:

function bubbleSort(arr) {
  const a = arr.slice();
  for (let i = 0; i < a.length; i++) {
    for (let j = 0; j < a.length - 1; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
      }
    }
  }
  return a;
}

This works — bubbleSort([3, 1, 2]) returns [1, 2, 3]. But try it on a reverse-sorted million-element array: bubbleSort([1000000, 999999, ..., 1]). That's n² comparisons, roughly a trillion operations. On a modern laptop, that's tens of minutes. Merge sort on the same input runs in about a second — n log n is roughly 20 million operations, five orders of magnitude less work. The bigger the input, the wider the gap. Bubble sort isn't wrong; it just stops being usable past a few thousand elements.

The working solution

function mergeSort(arr, compare = defaultCompare) {
  // Base case: an array of 0 or 1 elements is already sorted. We still
  // return a copy so the caller can never observe shared references.
  if (arr.length <= 1) return arr.slice();

  // Divide: split at the middle index. `slice` is O(n) per level and
  // allocates new arrays — that's the space cost of this implementation.
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid), compare);
  const right = mergeSort(arr.slice(mid), compare);

  // Conquer: merge two already-sorted arrays into one sorted array.
  return merge(left, right, compare);
}

function merge(left, right, compare) {
  const out = [];
  let i = 0;
  let j = 0;

  // Two-pointer walk: always pull the smaller front element.
  while (i < left.length && j < right.length) {
    // `<= 0` (not `< 0`) is what keeps the sort stable: when the two
    // candidates compare equal, we take from `left` first, so items
    // that started earlier in the input stay earlier in the output.
    if (compare(left[i], right[j]) <= 0) {
      out.push(left[i++]);
    } else {
      out.push(right[j++]);
    }
  }

  // One side is exhausted; append whatever remains of the other.
  // No comparisons needed — both inputs were already sorted.
  while (i < left.length) out.push(left[i++]);
  while (j < right.length) out.push(right[j++]);

  return out;
}

function defaultCompare(a, b) {
  // Sort numerically (and lexicographically for strings). We avoid
  // `a - b` because that returns NaN for non-numeric types and would
  // be incorrect for strings. The `<`/`>` form works for both.
  if (a < b) return -1;
  if (a > b) return 1;
  return 0;
}

module.exports = { mergeSort };

A few things in this code are doing real work, not just ceremony. The base case returns arr.slice() instead of arr itself — otherwise the caller would receive the same array reference for any single-element input and could accidentally mutate it later. The default parameter compare = defaultCompare lets a caller pass a custom comparator (descending, by property) while keeping the no-arg call site clean. The <= 0 in the merge is the one-character difference between a stable sort and an unstable one — see the diagram in the next section. And the two while drains at the end are how you avoid an else branch with extra bounds checks inside the main loop: once one pointer reaches its array's end, just copy the rest of the other side straight through.

Walking through one call

Trace mergeSort([38, 27, 43, 3, 9, 82, 10]) step by step. The recursion tree above is the picture; here's the same thing in prose so you can map the calls to the picture.

Call 1 (root): mergeSort([38, 27, 43, 3, 9, 82, 10]). length === 7, so we don't hit the base case. mid = floor(7 / 2) = 3. We slice into left = [38, 27, 43] (indices 0–2) and right = [3, 9, 82, 10] (indices 3–6). Recurse on both.

Sorting the left half: mergeSort([38, 27, 43]). mid = 1. left = [38], right = [27, 43]. The [38] call hits the base case and returns [38]. The [27, 43] call recurses again, splitting into [27] and [43], both base cases. Merge [27] with [43]: compare 27 < 43, push 27, drain 43 → [27, 43]. Now merge [38] with [27, 43]: compare 38 > 27, push 27, j=1. Compare 38 < 43, push 38, i=1 (left exhausted). Drain right → push 43. Result: [27, 38, 43].

Sorting the right half: mergeSort([3, 9, 82, 10]). mid = 2. Splits into [3, 9] and [82, 10]. The first recursion sorts [3, 9] (already in order) into [3, 9]. The second splits [82, 10] into [82] and [10], merges them as [10, 82]. Now merge [3, 9] with [10, 82]: 3 < 10 push 3, 9 < 10 push 9, left exhausted, drain [10, 82]. Result: [3, 9, 10, 82].

Final merge at the root. Merge [27, 38, 43] with [3, 9, 10, 82] (this is the merge traced in the diagram above): 27 > 3 push 3; 27 > 9 push 9; 27 > 10 push 10; 27 < 82 push 27; 38 < 82 push 38; 43 < 82 push 43; right has [82] left, drain it. Final: [3, 9, 10, 27, 38, 43, 82].

Complexity, the short version. The recursion tree has depth ⌈log₂(n)⌉ because each split halves the array. At every level of the tree, the merge step touches each of the n original elements exactly once (across all the merges at that level). So total work is O(n) per level times O(log n) levels = O(n log n). Space is O(n) for the extra arrays created at each level; this is the cost we pay for the simple recursive form.

Gotchas

• < instead of <= 0 in the merge breaks stability. Sort [{key: 1, id: 'a'}, {key: 1, id: 'b'}] by key with strict less-than and you can get back ['b', 'a'] because when the keys tie the algorithm pulls from the right half first. Tests that check stability with tagged objects will catch this immediately. Fix: use <= 0 so ties favor the left half.
• Calling arr.sort() with no comparator on [10, 2, 1] returns [1, 10, 2]. Array.prototype.sort's default converts to strings ('10' < '2' is true because '1' < '2'). If you forward to arr.sort() as a default, you'll fail the "sorts numerically by default" test. Fix: write a proper defaultCompare that uses < and > on the raw values.
• Returning arr directly in the base case mutates across calls. If mergeSort([42]) returns the same arr reference, then const x = [42]; mergeSort(x).push(99); mutates x. The test for "does not mutate the input" will fail on edge-case inputs. Fix: return arr.slice() in the base case.
• Computing mid as arr.length / 2 without Math.floor. JavaScript doesn't have integer division — slice(0, 3.5) happens to work (it floors internally) but the value 3.5 is a smell, and arr[3.5] elsewhere returns undefined. Fix: explicit Math.floor so the intent is clear and the variable is always an integer.
• Off-by-one in the slice: arr.slice(0, mid - 1) or arr.slice(mid + 1). The standard slice is [0, mid) and [mid, length) — the mid index goes to the right half because the left bound is exclusive. Drop or duplicate the mid element and you'll lose data or sort it twice. Fix: write the slice indices out on paper for a small input before trusting them.

Going further

• Bottom-up (iterative) merge sort. Instead of recursing, treat the input as n sorted runs of size 1, then iteratively merge pairs of adjacent runs into runs of size 2, then 4, then 8, until one run remains. Same O(n log n) time, no recursion stack, slightly trickier index math — this is the version most production sort libraries actually ship.
• Hybrid with insertion sort at small sizes. Recursion overhead dominates on tiny subarrays; switching to insertion sort once arr.length <= 16 is faster in practice. This is exactly what Timsort (Python's and V8's Array.prototype.sort) does, alongside the bottom-up structure above.
• External merge sort for files that don't fit in memory. Same algorithm, but the "split" is into chunks small enough to sort in RAM (written to temp files), and the "merge" is a k-way merge using a heap-keyed by the front of each file. This is how databases sort ORDER BY results that exceed work_mem.