Efficient In-Memory Merge: Merging Two Sorted Arrays for Optimal Performance

Photo by M. R. on Unsplash

You are given two integer arrays nums1 and nums2, sorted in increasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Python solution :

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        while m and n:
            if nums1[m-1] >= nums2[n-1]:
                nums1[m+n-1] = nums1[m-1]
                m -= 1
            else:
                nums1[m+n-1] = nums2[n-1]
                n -= 1
        if n > 0:
            nums1[:n] = nums2[:n]

Examine the last valid elements in nums1 and nums2. Transfer the larger one of the two elements to the very end of nums1.

If there are no more elements in the nums2 to copy, the process is complete.

If there are no more elements in nums1 to copy, perform a block copy of the remaining elements from nums2 to nums1.

Golang solution:

func merge(nums1 []int, m int, nums2 []int, n int)  {
    i, j, k := m-1, n-1, m+n-1

 for i >= 0 && j >= 0 {
  if nums1[i] >= nums2[j] {
   nums1[k] = nums1[i]
   i--
  } else {
   nums1[k] = nums2[j]
   j--
  }
  k--
 }

 for j >= 0 {
  nums1[k] = nums2[j]
  j--
  k--
 }
}

Rust solution :

impl Solution {
    pub fn merge(nums1: &mut Vec<i32>, m: i32, nums2: &mut Vec<i32>, n: i32) {
        let (mut m, mut n) = (m as usize, n as usize);

        while m > 0 && n > 0 {
            if nums1[m - 1] >= nums2[n - 1] {
                nums1[m + n - 1] = nums1[m - 1];
                m -= 1;
            } else {
                nums1[m + n - 1] = nums2[n - 1];
                n -= 1;
            }
        }

        if n > 0 {
            nums1[..n].copy_from_slice(&nums2[..n]);
        }
    }
}

Keyword usize is an unsigned integer type that represents the size of a pointer. Its size is platform-dependent and is typically either 32 or 64 bits, corresponding to the bit width of the memory addresses on the target system.

Keyword mut is short for "mutable." It is used to declare a variable as mutable, meaning that its value can be changed after it is initially assigned. In Rust, variables are immutable by default, which means you cannot modify their values once they are assigned.

nums1[..n] is a slice that includes the elements from index 0 to n-1 (exclusive) of the vector nums1 . The method copy_from_slice is then used to copy the elements from the second slice (&nums2[..n]) to the first slice (nums1[..n]). This method performs a memory copy from the source slice to the destination slice, ensuring that the destination slice has enough space to accommodate the elements from the source slice. So this is essentially copying the first n elements from nums2 to the beginning of nums1.

Time complexity: O(n)

Space complexity: O(1)