DSA interview question

Merge Two Sorted Arrays Without Extra Space

Medium · Algorithms · Topics: array, sorting, gap method

The problem

An embedded device holds two sorted arrays of sensor readings in fixed-size buffers, a (size n) and b (size m), and has no room for a third buffer. After a merge, a must hold the n smallest values in sorted order and b the remaining m values in sorted order. The standard merge needs O(n + m) extra memory, so it's off the table. Two in-place approaches work: swap misplaced elements across the boundary and then sort each array, or the gap method (a Shell-sort-style pass over both arrays treated as one).

Example: a = [1, 4, 8, 10], b = [2, 3, 9] → a = [1, 2, 3, 4], b = [8, 9, 10].

Function signature

void mergeSwapThenSort(vector<int>& a, vector<int>& b);  // swap across the boundary, then sort both
void mergeGap(vector<int>& a, vector<int>& b);           // gap method, O(1) extra space

Test cases

Input `(a, b)`	Output `(a, b)`	Explanation
`([1, 4, 8, 10], [2, 3, 9])`	`([1, 2, 3, 4], [8, 9, 10])`
`([1, 3, 5, 7], [0, 2, 6, 8, 9])`	`([0, 1, 2, 3], [5, 6, 7, 8, 9])`
`([10, 12], [5, 18, 20])`	`([5, 10], [12, 18, 20])`
`([1, 2], [3, 4])`	`([1, 2], [3, 4])`	Already in place
`([5], [])`	`([5], [])`	One side empty

(Confirm: both inputs are sorted; a keeps its size n and b its size m; no third array may be allocated.)

How interviewers phrase it

"Merge two sorted arrays without extra space" (GeeksforGeeks).
LeetCode 88 is related but easier: nums1 has spare slots at the end, so you merge from the back.

Clarifying questions to ask

Is any extra space allowed at all?
Should the first array end up with the n smallest values?
Are both arrays sorted non-decreasingly?

Follow-ups to expect

"How does the swap approach work?"
"Why does that swap loop stop at the right point?"
"How does the gap method work?"
"What about LeetCode 88?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview