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.
Want to improve your JavaScript? I have a list of recommended JavaScript books.