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.