Problem: Given two sorted arrays, merge them into a new array that is also sorted.

Example:

const arr1 = [3, 5, 6, 10, 11, 20];
const arr2 = [1, 2, 7, 8, 15, 19];

mergeTwo(arr1, arr2); // [1, 2, 3, 5, 6, 7, 8, 10, 11, 15, 19, 20]

First Approach

We can use the spread operator (or optionally concat()) to join the two lists and then sort the result.

// O(n log n) time & O(n) space
function mergeTwo(arr1, arr2) {
  let result = [...arr1, ...arr2];
  return result.sort((a,b) => a-b);
}

Greedy Approach

But given that the two arrays are already sorted we can use a greedy approach to go through each array and track the smallest element, each time adding it to a new merged array.

// O(n) time & O(n) space
function mergeTwo(arr1, arr2) {
  let merged = [];
  let index1 = 0;
  let index2 = 0;
  let current = 0;

  while (current < (arr1.length + arr2.length)) {
      let unmerged1 = arr1[index1];
      let unmerged2 = arr2[index2];

      // if next comes from arr1
      if (unmerged1 < unmerged2) {
          merged[current] = unmerged1;
          index1++;

      // if next comes from arr2
      } else {
          merged[current] = unmerged2;
          index2++;
      }

      current++;
  }

  return merged;
}

mergeTwo(arr1, arr2);
// [1, 2, 3, 5, 6, 7, 8, 10, 11, 15, 19, undefined]

This works but we have undefined at the end which will always happen since one of our arrays ran out of elements before we finished merging.

Greedy Approach (with edge cases)

To fix this bug, we need a way to handle the situation where one array is depleted but the other still has elements.

In other words, add the current item in arr1 to merged only if arr1 is not depleted and either arr2 is depleted or the current item in arr1 is less than the current item in arr2.

// O(n) time & O(n) space
function mergeTwo(arr1, arr2) {
  let merged = [];
  let index1 = 0;
  let index2 = 0;
  let current = 0;

  while (current < (arr1.length + arr2.length)) {

    let isArr1Depleted = index1 >= arr1.length;
    let isArr2Depleted = index2 >= arr2.length;

    if (!isArr1Depleted && (isArr2Depleted || (arr1[index1] < arr2[index2]))) {
      merged[current] = arr1[index1];
      index1++;
    } else {
      merged[current] = arr2[index2];
      index2++;
    }

    current++;
  }

  return merged;
}

mergeTwo(arr1, arr2);
// [1, 2, 3, 5, 6, 7, 8, 10, 11, 15, 19, 20]

Extra Credit

What about merging multiple sorted arrays? In other words one of the inputs is an array of sorted arrays and outputs a single sorted array with all the items from each array?

We need a way to flatten the arrays into two arrays for comparison, which can be done as follows:

const flatten = arr => [].concat(...arr);

So a simple way would be to run flatten on the array of arrays and then use the result in our existing mergeTwo function.

Note that this approach doesn’t work on huge (eg 200,000+ elements) arrays. Instead see here on Stack Overflow.



Want to improve your JavaScript? I have a list of recommended JavaScript books.