Cracking the Coding Interview 6thE 10.1 Sorted Merge
“Sorted Merge: You are given two sorted arrays, A and B, where A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order.”
Arrays are already sorted, so we can just do an insertion sort: iterate both, taking the next sorted item from each and insert it into A which has space for both.
It would be tricky to insert at the beginning, though, as we’d have to shift the existing elements in A. So we can do the insertion sort in reverse order, taking the largest element at a time from the end of each array and adding it to the moving end of A.
Solving this in JS, which doesn’t really have allocated arrays, but simulating
that with null items.
function sortedMergeInPlace(arrayA, arrayB) {
let indexA = (arrayA.length - arrayB.length) - 1;
let indexB = arrayB.length - 1;
let indexMerged = arrayA.length - 1;
while (indexMerged >= 0) {
if (indexA >= 0 && arrayA[indexA] > arrayB[indexB]) {
arrayA[indexMerged] = arrayA[indexA];
indexA--;
} else {
// We've either run out of A items, or B is larger.
arrayA[indexMerged] = arrayB[indexB];
indexB--;
}
indexMerged--;
}
}
const A = [3, 5, 6, 7, 8, null, null, null];
const B = [2, 4, 9];
sortedMergeInPlace(A, B);
console.log(JSON.stringify(A));
// [2, 3, 4, 5, 6, 7, 8, 9]