Merge two sorted arrays without extra space

Hard

Problem

Two sorted arrays a (size n) and b (size m) are given. Rearrange their elements in place so that a holds the n smallest values and b holds the rest, both still sorted. Use O(1) extra space.

Example 1

Input:  a = [1, 4, 7, 8, 10], b = [2, 3, 9]
Output: a = [1, 2, 3, 4, 7], b = [8, 9, 10]

Also asked as: Merge 2 sorted arrays without using Extra space

Test cases

Case 1

Input:    [1,4,7,8,10], [2,3,9]
Expected: [1,2,3,4,7]

Case 2

Input:    [10,12], [5,18,20]
Expected: [5,10]

Case 3

Input:    [1,2,3], [4,5]
Expected: [1,2,3]

Case 4

Input:    [5], [1]
Expected: [1]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Gap method (Shell-sort style)

Time O((n+m) log(n+m))Space O(1)

Start with gap = ceil((n+m)/2); compare and swap elements `gap` apart across both arrays; halve the gap until 1.

function mergeInPlace(a, b) {
const n = a.length, m = b.length, total = n + m;
const at = (i) => (i < n ? a[i] : b[i - n]);
const set = (i, v) => { if (i < n) a[i] = v; else b[i - n] = v; };
let gap = Math.ceil(total / 2);
while (gap > 0) {
for (let i = 0; i + gap < total; i++) {
if (at(i) > at(i + gap)) {
const t = at(i); set(i, at(i + gap)); set(i + gap, t);
}
}
gap = gap === 1 ? 0 : Math.ceil(gap / 2);
}
}