easy

Merge Two Sorted Arrays

Merge two sorted arrays into one sorted array.

1. Define the problem

Merge Two Sorted Arrays

Given two integer arrays arr1 and arr2, each already sorted in non-decreasing order , return a new array containing every element from both, sorted in non-decreasing order. Do not modify arr1 or arr2 — build the result in a separate array. Use two pointers , one per array, always taking the smaller front value and advancing only that pointer.

Constraints

  • 0 ≤ arr1.length, arr2.length ≤ 1000
  • -104 ≤ arr1i, arr2i ≤ 104
  • arr1 and arr2 are each sorted in non-decreasing order

Example

Inputarr1 = [1, 3, 5], arr2 = [2, 4, 6]
Output[1, 2, 3, 4, 5, 6]

Explanation Walking both arrays front to back and always taking the smaller value produces [1, 2, 3, 4, 5, 6].

2. Know the words first

In plain terms

Non-decreasing order
Each value is greater than or equal to the one before it, so repeats are allowed — for example, [1, 2, 2, 5] is in non-decreasing order.
3. Visualize the solution

Walk both arrays, write the smaller front value each step

Walk both arrays, write the smaller front value each step
Statusinit

i=0 (arr1[0]=1), j=0 (arr2[0]=2). 1 ≤ 2, so take from arr1.

What happens in this step

arr1 = [1, 3, 5]   i=0
arr2 = [2, 4, 6]   j=0
result = []

Compare arr1[0]=1 vs arr2[0]=2. 1 is smaller, so it is written first and i advances to 1.
Step 1 of 6

Steps to visualize

  1. Point i at the start of arr1 and j at the start of arr2.
  2. Compare arr1i and arr2j; write whichever is smaller into the next slot of the result and move that pointer forward.
  3. Repeat until one array is fully consumed.
  4. Copy any remaining elements from the other array onto the end of the result.
  5. The result is fully sorted once every element has been written.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Walk both arrays, write the smaller front value each step
Statusinit

i=0 (arr1[0]=1), j=0 (arr2[0]=2). 1 ≤ 2, so take from arr1.

What happens in this step

arr1 = [1, 3, 5]   i=0
arr2 = [2, 4, 6]   j=0
result = []

Compare arr1[0]=1 vs arr2[0]=2. 1 is smaller, so it is written first and i advances to 1.
Step 1 of 6
5. Solution

Solution

solution.tsTypeScript
function mergeTwoSortedArrays(arr1, arr2) {
  const result = [];
  let i = 0;
  let j = 0;

  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] <= arr2[j]) {
      result.push(arr1[i]);
      i++;
    } else {
      result.push(arr2[j]);
      j++;
    }
  }

  while (i < arr1.length) {
    result.push(arr1[i]);
    i++;
  }

  while (j < arr2.length) {
    result.push(arr2[j]);
    j++;
  }

  return result;
}
Time
O(n + m)
Space
O(n + m)
6. Test cases

Test cases

InputExpectedCovers
arr1 = [1, 3, 5], arr2 = [2, 4, 6][1, 2, 3, 4, 5, 6]example from the docstring
arr1 = [], arr2 = [1, 2, 3][1, 2, 3]first array is empty
arr1 = [4, 5], arr2 = [][4, 5]second array is empty
arr1 = [], arr2 = [][]both arrays are empty
arr1 = [1, 1, 3], arr2 = [1, 2, 2][1, 1, 1, 2, 2, 3]duplicate values shared across both arrays
arr1 = [1, 2, 3], arr2 = [4, 5, 6][1, 2, 3, 4, 5, 6]every value in arr1 is smaller than every value in arr2
arr1 = [7, 8], arr2 = [1, 2, 3][1, 2, 3, 7, 8]every value in arr2 is smaller than every value in arr1
arr1 = [5], arr2 = [3][3, 5]smallest non-trivial case, one element in each array

Keep reading