Solutions

1. Sorting

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.
        """
        nums1[m:] = nums2[:n]
        nums1.sort()

Time & Space Complexity

Time complexity: $O((m + n) \log (m + n))$
Space complexity: $O(1)$ or $O(m + n)$ depending on the sorting algorithm.

Where $m$ and $n$ represent the number of elements in the arrays $nums1$ and $nums2$ , respectively.

2. Three Pointers With Extra Space

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.
        """
        nums1_copy = nums1[:m]
        idx = 0
        i = j = 0
        while idx < m + n:
            if j >= n or (i < m and nums1_copy[i] <= nums2[j]):
                nums1[idx] = nums1_copy[i]
                i += 1
            else:
                nums1[idx] = nums2[j]
                j += 1
            idx += 1

Time & Space Complexity

Time complexity: $O(m + n)$
Space complexity: $O(m)$

Where $m$ and $n$ represent the number of elements in the arrays $nums1$ and $nums2$ , respectively.

3. Three Pointers Without Extra Space - I

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.
        """
        last = m + n - 1

        # Merge in reverse order
        while m > 0 and n > 0:
            if nums1[m - 1] > nums2[n - 1]:
                nums1[last] = nums1[m - 1]
                m -= 1
            else:
                nums1[last] = nums2[n - 1]
                n -= 1
            last -= 1

        # Fill nums1 with leftover nums2 elements
        while n > 0:
            nums1[last] = nums2[n - 1]
            n -= 1
            last -= 1

Time & Space Complexity

Time complexity: $O(m + n)$
Space complexity: $O(1)$ extra space.

Where $m$ and $n$ represent the number of elements in the arrays $nums1$ and $nums2$ , respectively.

4. Three Pointers Without Extra Space - II

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.
        """
        last = m + n - 1
        i, j = m - 1, n - 1

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

            last -= 1

Time & Space Complexity

Time complexity: $O(m + n)$
Space complexity: $O(1)$ extra space.

Where $m$ and $n$ represent the number of elements in the arrays $nums1$ and $nums2$ , respectively.