Day 10: Merge Sort

DAY 10 / 30 · WEEK 2

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

             [5, 2, 8, 1]

    Split        ↙  ↘

       [5, 2]    [8, 1]

Split  ↙  ↘      ↙  ↘

[5]  [2]   [8]  [1]

Merge  ↘  ↙      ↘  ↙

       [2, 5]    [1, 8]

    Merge    ↖  ↗

        [1, 2, 5, 8]

The top half shows splitting (recursion going down). The bottom half shows merging (recursion returning back up) — one merge per level, combining sorted halves into larger sorted ranges.

Interactive visualization: full sort, split + merge

Legend:

• ■ being merged (this level)
• ■ just placed
• ■ fully merged, this range done

Running example: merge sort on [5, 2, 8, 1, 9, 3]

Press Play or Step to begin.

Step 0 / 0

▶ PlayStep ⏭⟲ Reset🔀 Shuffle

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])

i	j	left[i]	right[j]	Action	result
0	0	2	1	1 < 2 → take right	[1]
0	1	2	8	2 < 8 → take left	[1, 2]
1	1	5	8	5 < 8 → take left	[1, 2, 5]
2	1	—	8	left exhausted → take remaining right	[1, 2, 5, 8]

Complexity

Approach	Time	Space	Why
Merge sort	O(n log n)	O(n)	log n levels of splitting, O(n) work merging at each level; needs extra arrays to merge into.
Bubble/Selection/Insertion (Day 8)	O(n²)	O(1)	No splitting — comparisons scale with n², not n log n.

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

1. Merge Sorted Array — Easy

LeetCode: Merge Sorted Array

Merge two sorted arrays into the first one, in place (the first array has extra trailing space to hold the result).

Hint

Merging from the front (like today’s lesson) means shifting elements out of the way. What happens if you merge from the back instead, comparing the largest remaining elements first?

Show solution

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;
}

2. Sort an Array — Medium

LeetCode: Sort an Array

Sort an array of integers in ascending order — implement the sort yourself.

Hint

The array sizes in this problem’s constraints are big enough that Day 8’s O(n²) sorts will time out — you need something that scales as O(n log n) instead. What did you just build?

Show solution

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));
}

3. Merge k Sorted Lists — Hard

LeetCode: Merge k Sorted Lists

Given k sorted linked lists, merge them into one sorted list. (A preview — we build linked lists properly on Day 15. For now, just think through the approach in terms of arrays.)

Hint

You already know how to merge 2 sorted lists in one pass. Merge k lists the same way merge sort merges sub-arrays: pair them up and merge two at a time, then merge those results, repeating until one list remains.

Show solution

// 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

Question 1

What’s the time complexity of merge sort?

• O(n log n) — correct
• O(n²)
• O(n)

Explanation: log n levels of splitting, each doing O(n) total work to merge — multiply them together for O(n log n).

Question 2

Before calling merge(left, right), what must be true?

• Both left and right are already fully sorted — correct
• left and right must be the same length
• Nothing — merge works on any two arrays

Explanation: Both halves are recursively sorted first — merge only works correctly on two already-sorted inputs.

Question 3

What’s the extra space complexity of merge sort?

• O(1)
• O(n) — correct
• O(log n)

Explanation: Merging needs a new array to write results into as it walks both sorted halves.

Question 4

Which comparison in merge() keeps merge sort stable?

• left[i] <= right[j] (prefer left on ties) — correct
• left[i] < right[j] (strict, no tie preference)
• Neither — merge sort is never stable

Explanation: Using <= (not strict <) means the left element wins ties, preserving the original relative order of equal elements — that’s what makes merge sort stable.

Question 5

Why does splitting an array in half repeatedly take log n levels?

• Halving the size each time means only ~log₂(n) splits reach size 1 — correct
• It always takes exactly n splits
• It’s always exactly 2 splits, regardless of n

Explanation: Each split halves the array’s size — you can only halve n about log₂(n) times before reaching size 1.