DAY 10 / 30 · WEEK 2

Merge Sort

Goal of the day

• Implement merge sort: divide the array in half recursively, then merge sorted halves back together.
• Understand why splitting in half repeatedly gives O(n log n) — genuinely faster than Day 8's O(n²) sorts.
• Merge two already-sorted arrays using the two-pointer technique from Day 4.

Concept

Split a deck of cards in half. Then split each half in half again. Keep going until every pile has exactly one card — a pile of one card is trivially "sorted." Now merge piles back together two at a time: look at the top card of each pile, take the smaller one, repeat. Merging two already-sorted piles into one sorted pile only takes one pass through both — that's Day 4's two-pointer merge, reused here as the combining step.

The splitting takes log n levels (each split halves the size, and you can only halve n about log₂n times before reaching size 1). At every level, merging all the pieces back together costs O(n) total work. log n levels × O(n) work per level = O(n log n) — the same shape of growth curve you saw on Day 2, and genuinely faster than O(n²) for any reasonably large input.

Diagram

Interactive visualization: full sort, split + merge

The code

function mergeSort(arr) {
  if (arr.length <= 1) return arr; // base case: 1 element is already sorted
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));   // recursively sort left half
  const right = mergeSort(arr.slice(mid));     // recursively sort right half
  return merge(left, right);                   // combine two sorted halves
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }
  while (i < left.length) result.push(left[i++]);   // leftover left elements
  while (j < right.length) result.push(right[j++]); // leftover right elements
  return result;
}

Line by line:

• mergeSort's base case is an array of 0 or 1 elements — trivially sorted, nothing to do. This is Day 9's recursion pattern applied to sorting.
• Both halves are fully sorted before merge is ever called — that's what guarantees merge can just walk both arrays once with two pointers, exactly like Day 4's converging two-pointer pattern.
• The two trailing while loops handle leftovers when one side runs out before the other — easy to forget, and the #1 source of merge-sort bugs.

Dry run: merge([2, 5], [1, 8])

Complexity

Merge sort trades space for time: it needs O(n) extra memory for the merge step, but its time complexity is a full complexity class better than Day 8's sorts — the gap between O(n log n) and O(n²) that Day 2's growth chart showed becomes very real for large inputs.

Interview corner

• Why is merge sort O(n log n) and not O(n²)? The array is split in half log n times (that's the "log n" part), and merging everything back together at each of those log n levels costs O(n) total (that's the "n" part) — multiply them together.
  ↳ Common follow-up: "Prove the merging at each level is O(n)." Every element gets compared and placed exactly once per level, regardless of how many sub-arrays that level is split into — so each level costs O(n) total, not more.
• Is merge sort stable? Yes — the merge step's left[i] <= right[j] comparison (using <=, not <) always prefers the left element on ties, preserving original relative order.
  ⚠ Trap: flip that to strict < and stability quietly breaks — equal elements from the right half can jump ahead of equal elements from the left half. Always double check the comparison operator when asked about stability.
• Can you merge sort in place, without the O(n) extra space? Not easily — true in-place merging exists but is significantly more complex and slower in practice. Most real implementations accept the O(n) space cost. Knowing this trade-off exists (and why nobody bothers with the complex in-place version) is worth mentioning if asked.

How to talk through it out loud: narrate the three-part shape of every divide-and-conquer solution — "split the problem in half, recursively solve each half, then combine the two answers." Naming which part is the base case, which is the divide step, and which is the combine step shows structural understanding, not just a memorized implementation.

Practice problems

function merge(nums1, m, nums2, n) {
  let i = m - 1, j = n - 1, k = m + n - 1;
  while (j >= 0) {
    if (i >= 0 && nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
    else nums1[k--] = nums2[j--];
  }
  return nums1;
}

function sortArray(nums) {
  if (nums.length <= 1) return nums;
  const mid = Math.floor(nums.length / 2);
  const left = sortArray(nums.slice(0, mid));
  const right = sortArray(nums.slice(mid));
  return merge(left, right);
}
function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    result.push(left[i] <= right[j] ? left[i++] : right[j++]);
  }
  return result.concat(left.slice(i)).concat(right.slice(j));
}

// Array-based sketch of the idea (real linked-list version on Day 15):
function mergeKSorted(lists) {
  if (lists.length === 0) return [];
  if (lists.length === 1) return lists[0];
  const mid = Math.floor(lists.length / 2);
  const left = mergeKSorted(lists.slice(0, mid));
  const right = mergeKSorted(lists.slice(mid));
  return merge(left, right); // same merge() from today
}

Quiz