88. Merge Sorted Array

Merge sorted array gives us one array with extra space to hold onto all the items of a secondary array. Both are sorted. We want to merge them in one pass.

We have 3 pointers: one at the end of the first list, one at the end of the second list, and one at the location where we want to put the largest item from both lists. If we find an item is larger in either list, we put it at the end of the first list, and decrement the pointer where the item is.

We do this for the entire array.

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        p1 = m - 1
        p2 = n - 1
 
        for p in range(n + m - 1, -1, -1):
            if p2 < 0:
                break
            if p1 >= 0 and nums1[p1] > nums2[p2]:
                nums1[p] = nums1[p1]
                p1 -= 1
            else:
                nums1[p] = nums2[p2]
                p2 -= 1