Merge Sorted Arrays

Given two sorted integer arrays, nums1 and nums2, and the number of data elements in each array, m and n, implement a function that merges the second array into the first one. You have to modify nums1 in place.

Merge Sorted Array

Problem Statement

You are given two sorted integer arrays, nums1 and nums2. You are also given m and n, which tell you how many actual data elements are in each array.

Your task is to merge nums2 into nums1, so that nums1 becomes one single sorted array. You must change nums1 in place (without creating a new array).

Note: Assume nums1 has a size equal to m + n. This means it already has enough empty space at the end to hold all the elements from nums2.

Constraints

• nums1.length = m + n
• nums2.length = n
• 0 ≤ m, n ≤ 200
• 1 ≤ m + n ≤ 200
• −10³ ≤ nums1[i], nums2[j] ≤ 10³

Examples

Example 1

Input:

• nums1 = [3, 4, 9, 0, 0, 0], m = 3
• nums2 = [1, 2, 7], n = 3

Output: [1, 2, 3, 4, 7, 9]

Example 2

Input:

• nums1 = [1, 4, 9, 0, 0], m = 3
• nums2 = [1, 7, 6], n = 2

Output: [1, 1, 4, 9, 7, 6]

Solution

We start comparing from the end of both arrays, not the beginning. This lets us fill in nums1 from the back, without overwriting any values we still need.

Steps

• We set up two pointers:
  • p1, starting at the last real data element in nums1 (index m - 1).
  • p2, starting at the last element in nums2 (index n - 1).
• We also use a third pointer, p, starting at the very last index of nums1 (index m + n - 1). This is where we'll place the next value.
• We compare nums1[p1] and nums2[p2]:
  • Whichever value is larger, we place it at position p in nums1. Then we move that pointer (p1 or p2) one step back.
  • We always move p one step back after placing a value.
• We keep doing this until we've placed all the remaining elements from nums2. Since nums1 is being filled from the back, we don't need to worry about nums1's own remaining elements — they're already in the correct sorted spot.

Code

function mergeSorted(nums1, m, nums2, n) {
    let p1 = m - 1;
    let p2 = n - 1;

    for (let p = n + m - 1; p > -1; p--) {
        if (p2 < 0) {
            break;
        }

        if (p1 >= 0 && nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1 -= 1;
        } else {
            nums1[p] = nums2[p2];
            p2 -= 1;
        }
    }
    return nums1;
}