Skip to content

Instantly share code, notes, and snippets.

@rakin92
Created September 5, 2019 05:19
Show Gist options
  • Save rakin92/0c28a4756ecee2afa953d6904d77fb9a to your computer and use it in GitHub Desktop.
Save rakin92/0c28a4756ecee2afa953d6904d77fb9a to your computer and use it in GitHub Desktop.
const arr1 = [3, 5, 6, 10, 11, 18, 21];
const arr2 = [1, 2, 7, 8, 15, 19];
// O(n log n)
function mergeTwo(arr1, arr2) {
let result = [...arr1, ...arr2];
return result.sort((a,b) => a-b);
}
console.log(mergeTwo(arr1, arr2));
// O(n)
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;
}
console.log(mergeTwo(arr1, arr2));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment