Merge Two Sorted Arrays Without Extra Space

The problem has two variations. For the first variation, we need to merge two sorted arrays into an existing array (can be a separate third array or one of the two arrays) having length of (m + n) where m and n are the length of the sorted portions of the arrays which concern us. The idea is to use two pointers from the end, compare the elements, choose the maximum one, place that at the end of the resultant array and decrease the pointer whom we have chosen. Note that any values in the in the m to m + n - 1 indices of the larger array will be overwritten as a result of this algorithm.

Problem Link - Variation 1

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        i = m + n - 1
        p1 = m - 1
        p2 = n - 1

        while p1 >= 0 and p2 >= 0:
            if nums1[p1] > nums2[p2]:
                nums1[i] = nums1[p1]
                p1 -= 1
            else:
                nums1[i] = nums2[p2]
                p2 -= 1

            i -= 1

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

        while p2 >= 0:
            nums1[i] = nums2[p2]
            p2 -= 1
            i -= 1

The other variation has no extra space in any of the arrays, the arrays needs to be merged via rearranging the elements in place. The idea for solving the variation 2 of the problem comes from shell sort.

Note: To calculate ceil of a number divided by 2, we can use (num >> 1) + (num & 1)

Problem Link - Variation 2

class Solution:
    def swap_if_left_greater(self, a: list[int], b: list[int], l: int, r: int) -> None:
        # Swap two numbers using the XOR method without using a temporary variable
        # Works only in case of numbers, otherwise use third variable method
        if a[l] > b[r]:
            a[l] = a[l] ^ b[r]
            b[r] = a[l] ^ b[r]
            a[l] = a[l] ^ b[r]
        return


    def mergeArrays(self, a: list[int], b: list[int]) -> None:
        m, n = len(a), len(b)
        k = m + n

        # This is to compute math.ceil(k // 2)
        gap = (k >> 1) + (k & 1)

        while gap > 0:
            l, r = 0, gap

            while r < k:
                if l < m and r >= m:
                    # l in a, r in b
                    self.swap_if_left_greater(a, b, l, r - m)
                elif l >= m:
                    # l, r both in b
                    self.swap_if_left_greater(b, b, l - m, r - m)
                elif r < m:
                    # l, r both in a
                    self.swap_if_left_greater(a, a, l, r)

                l += 1
                r += 1

            # We need to break if gap is equal to 1 else math.ceil(1 // 2) is also 1
            # So if we don't break, we get stuck in an infinite loop
            if gap == 1:
                break

            # This is to compute math.ceil(gap // 2)
            gap = (gap >> 1) + (gap & 1)