"""
Time complexity: O(n+m)

We are performing n+2⋅mn + 2 \cdot mn+2⋅m reads and n+2⋅mn + 2 \cdot mn+2⋅m writes. Because constants are ignored in Big O notation, this gives us a time complexity of O(n+m)\mathcal{O}(n + m)O(n+m).

Space complexity: O(m)
We are allocating an additional array of length mmm.
"""

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.
        """

        nums3 = nums1[:m]
        first = 0
        second = 0
        third = 0

        while (first < n+m):
            if ((second <n and third < m) and nums3[third] <= nums2[second]) or second>=n:
                nums1[first] = nums3[third]
                third += 1
            elif ((second < n and third < m) and nums3[third] > nums2[second]) or first>=m:
                nums1[first] = nums2[second]
                second += 1
            first += 1