88. Merge Sorted Array

main idea: there are two thoughts to start inserting number with correct order - 1. start with smallest 2. start with largest; but the problem with start with smallest is that once number from nums2 need to occupy non-empty position in nums1, it’s hard to reposition original number in nums1; it will cause more steps to make nums1 in order. Therefore, it will be ideal to start with largetst number since the position in nums1 is empty so no number will be overwritten. With help of pointers keep tracking leftover numbers in nums1 and nums2 and ordered final nums1, each insertion will keep nums1[p:] in order all the time

corner case, when p1 in nums1 has reached to head but p2 in nums2 has not yet. we need to keep inserting num in nums2 into nums1 since nums2 is already sorted locally

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