# JavaScript: Merge Two Sorted Arrays

**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.