CPU: O(n)
Memory: O(n)

from typing import List

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.
        """
        i = m-1 # point to last element of nums1
        j = n-1 # point to last element of nums2
        k = m+n-1 # point to the last position of merged array

        while i >= 0 and j >= 0:
            if nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                k -= 1
                i -= 1
            else:
                nums1[k] = nums2[j]
                k -= 1
                j -= 1

        while i >= 0:
            nums1[k] = nums1[i]
            k -= 1
            i -= 1

        while j >= 0:
            nums1[k] = nums2[j]
            k -= 1
            j -= 1

def main():
    s = Solution()

    nums1 = [1, 2, 3, 0, 0, 0]
    nums2 = [2, 5, 6]

    s.merge(nums1, 3, nums2, 3)

    print(nums1)

if __name__ == '__main__':
    main()