How to Merge Two Sorted Arrays?

By Prajwal Haniya

Techletter #30 | May 24, 2023

The hard truth is, just going through only concepts doesn’t make us good at problem-solving. We need to start solving data structure problems. So, here we go with our problem.

Problem statement: You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

The above problem statement is derived from the leetcode: You can explore the problem here Link

// Inputs
arr1 = [1, 3, 5, 0, 0, 0];
m = 3
arr2 = [2,4,6];
n = 3

// output
arr1 = [1, 2, 3, 4, 5, 6];

I tried out different ways but, the below code was clean and understandable. As the array is sorted you can easily start comparing from the end of the array.

function merge(nums1, m, nums2, n) {
  let i = m - 1;
  let j = n - 1;
  let k = m + n - 1;

  while (i >= 0 && j >= 0) {
    if (nums1[i] > nums2[j]) {
      nums1[k] = nums1[i];
      i--;
    } else {
      nums1[k] = nums2[j];
      j--;
    }
    k--;
  }

  // Copy remaining elements from nums2 to nums1
  while (j >= 0) {
    nums1[k] = nums2[j];
    j--;
    k--;
  }
}

Let’s see each iteration with an example

// Sorted array with additional space
const nums1 = [1, 3, 5, 0, 0, 0]; 
// Number of elements in nums1
const m = 3; 

const nums2 = [2, 4, 6]; 
const n = 3; 

// Step 1: Initialize pointers
i = 2, j = 2, k = 5

// Step 2: Compare and merge elements
nums1[k] = 6 (since nums1[i] > nums2[j])
// Result: nums1 = [1, 3, 5, 0, 0, 6]
i = 1, j = 2, k = 4

nums1[k] = 5 (since nums1[i] > nums2[j])
// Result: nums1 = [1, 3, 5, 0, 5, 6]
i = 1, j = 1, k = 3

nums1[k] = 4 (since nums1[i] > nums2[j])
// Result: nums1 = [1, 3, 4, 4, 5, 6]
i = 1, j = 0, k = 2

nums1[k] = 3 (since nums1[i] > nums2[j])
// Result: nums1 = [1, 3, 3, 4, 5, 6]
i = 0, j = 0, k = 1

nums1[k] = 2 (since nums1[i] > nums2[j])
// Result: nums1 = [1, 2, 3, 4, 5, 6]
i = 0, j = -1, k = 0

// Step 3: Copy remaining elements from nums2 to nums1
nums1[k] = 1
// Result: nums1 = [1, 2, 3, 4, 5, 6]

// Final merged and sorted array: [1, 2, 3, 4, 5, 6]

The time complexity of the merge function you provided is O(m + n), where m and n are the lengths of nums1 and nums2, respectively.