Merge two sorted arrays without extra space
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]
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); }}