mergeSortedArray.md

Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Example:

**Input:**
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

**Output:** [1,2,2,3,5,6]

Solution:

Using two pointers to traverse and compare integers from nums1 (to m) and nums2, and use another pointer to traverse nums1 as a whole array.

Code:

def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        p1 = m - 1
        p2 = n - 1
        p = m + n - 1
        
        while p1 >= 0 and p2 >= 0:
            if nums1[p1] > nums2[p2]:
                nums1[p] = nums1[p1]
                p1-=1
            else:
                nums1[p] = nums2[p2]
                p2-=1
            p-=1
        nums1[:p2+1] = nums2[:p2+1]