Merge Sorted Array

The problem. nums1 has length m + n: its first m values are sorted, and the last n slots are empty (zeros). nums2 holds n sorted values. Merge nums2 into nums1 in place so that nums1 becomes one sorted array. Return nothing.

Example

nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3  ->  nums1 = [1,2,2,3,5,6]
nums1 = [1], m = 1, nums2 = [], n = 0                ->  nums1 = [1]
nums1 = [0], m = 0, nums2 = [1], n = 1               ->  nums1 = [1]

The pattern: merge sort tricks

Merge sort's merge step — walk two sorted lists, repeatedly taking the smaller front value — is worth knowing on its own. It merges sorted arrays and linked lists in linear time, and because both halves are sorted while merging, it can also count relationships between the halves that would otherwise take O(n²): inversions, reverse pairs, smaller numbers after each value. This chapter goes from the plain merge to those counting tricks.

1. Copy nums2 in, then sort

1function merge(nums1, m, nums2, n) {2  for (let j = 0; j < n; j++) nums1[m + j] = nums2[j];   // fill the empty slots3  nums1.sort((a, b) => a - b);4}

Time O((m + n) log(m + n)), space O(1) beyond the sort. It ignores that both inputs are already sorted.

2. Merge forwards from a copy of nums1

1function merge(nums1, m, nums2, n) {2  const first = nums1.slice(0, m);                      // save nums1's values before overwriting3  let i = 0, j = 0, k = 0;4  while (i < m && j < n) nums1[k++] = first[i] <= nums2[j] ? first[i++] : nums2[j++];5  while (i < m) nums1[k++] = first[i++];6  while (j < n) nums1[k++] = nums2[j++];7}

Time O(m + n), space O(m). A normal merge — but merging into the front of nums1 would overwrite values not yet used, hence the copy.

3. Merge from the back, in place

1function merge(nums1, m, nums2, n) {2  let i = m - 1;3  let j = n - 1;4  let k = m + n - 1;5  while (j >= 0) {6    if (i >= 0 && nums1[i] > nums2[j]) {7      nums1[k] = nums1[i];8      i--;9    } else {10      nums1[k] = nums2[j];11      j--;12    }13    k--;14  }15}

Time O(m + n), space O(1). Writing from the back is safe: k is always at or beyond i, so a slot is only overwritten once its value has been moved. When nums2 runs out, the rest of nums1 is already in place — that's why the loop only runs while j >= 0.

Comparing the approaches

Edge cases to test

Variations