Merge Sorted Array: Merge In-Place by Filling From the Back
Merge two sorted arrays in-place with the reverse three-pointer trick — fill nums1 from the back to avoid overwriting, with a walkthrough, code, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Merge Sorted Array looks trivial until you read the constraint that makes it interview material: you must merge the two arrays in-place, inside the first array, using no extra space. That single rule breaks the obvious approach and forces a small but genuinely clever reframe.
The trick is to stop thinking about the smallest element and start thinking about the largest. Fill from the back, and the whole problem collapses into a clean single pass. This is the reverse three-pointer pattern, and once you see it you'll reach for it every time an in-place merge shows up.
The problem
You're given two integer arrays nums1 and nums2, each already sorted in non-decreasing order, plus two integers m and n — the number of real elements in each. nums1 has length m + n: the first m slots hold its real values, and the last n slots are zeros reserved as scratch space. Merge nums2 into nums1 so nums1 ends up sorted. There is no return value; you mutate nums1 directly.
Input: nums1 = [1, 2, 3, 0, 0, 0], m = 3
nums2 = [2, 5, 6], n = 3
Output: nums1 = [1, 2, 2, 3, 5, 6]Two details drive the whole solution:
nums1is the destination, and it already contains live data in its front half. Any value you write can clobber a value you haven't merged yet.- Those trailing zeros are not data — they're empty write slots. There are exactly
nof them, matching thenelements coming fromnums2.
The brute force baseline
The naive move is to copy nums2 into the empty tail of nums1 and sort the whole thing.
function merge(nums1, m, nums2, n) {
for (let i = 0; i < n; i++) {
nums1[m + i] = nums2[i];
}
nums1.sort((a, b) => a - b);
}It's correct and short, but it throws away the most valuable fact in the problem: both inputs are already sorted. Sorting from scratch costs O((m + n) log(m + n)) and completely ignores the ordering you were handed for free. An interviewer will nod, then immediately ask you to do it in linear time. That's the real question.
Why filling from the front fails
The instinct from classic merge-sort is to compare fronts and take the smaller element. But the smallest merged value belongs at nums1[0] — a slot that already holds a real element you still need to compare. Writing there destroys data.
You could shift everything right to make room, but that turns every insertion into an O(m) move and drags you back to O(m·n). The forward direction fights the layout.
Flip it around. The largest merged value belongs at nums1[m + n - 1] — the very last slot, which is guaranteed to be empty scratch space. Placing the biggest element there can never overwrite anything unmerged, because everything to its left is either a value still waiting to be read or another empty slot. Filling back-to-front turns the destructive-write problem into no problem at all.
The optimal solution
Walk three pointers from the right: p1 on the last real nums1 element, p2 on the last nums2 element, and write on the final slot. At each step, copy the larger of the two tail values into write, then step that pointer and write left.
var merge = function (nums1, m, nums2, n) {
let p1 = m - 1;
let p2 = n - 1;
let write = m + n - 1;
while (p1 >= 0 && p2 >= 0) {
if (nums1[p1] > nums2[p2]) {
nums1[write] = nums1[p1];
p1 -= 1;
} else {
nums1[write] = nums2[p2];
p2 -= 1;
}
write -= 1;
}
while (p2 >= 0) {
nums1[write] = nums2[p2];
p2 -= 1;
write -= 1;
}
};Two things make this airtight. First, the main loop runs only while both arrays still have candidates. Second, the cleanup loop drains nums2. Notice there is no matching drain loop for nums1 — if nums2 empties first, the remaining nums1 values are already sitting in their correct positions, so there is nothing to move. That asymmetry is a feature of writing into nums1 itself.
The > comparison (take from nums2 on ties) keeps equal elements stable, which matters when you extend this pattern to objects rather than raw numbers.
Walkthrough
Tracing nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3. Pointers start at p1 = 2, p2 = 2, write = 5.
| p1 | p2 | write | nums1[p1] vs nums2[p2] | Take | nums1 after write |
|---|---|---|---|---|---|
| 2 | 2 | 5 | 3 vs 6 | nums2 → 6 | [1, 2, 3, 0, 0, 6] |
| 2 | 1 | 4 | 3 vs 5 | nums2 → 5 | [1, 2, 3, 0, 5, 6] |
| 2 | 0 | 3 | 3 vs 2 | nums1 → 3 | [1, 2, 3, 3, 5, 6] |
| 1 | 0 | 2 | 2 vs 2 | nums2 → 2 | [1, 2, 2, 3, 5, 6] |
After the fourth write, p2 drops to -1, so the main loop exits and the drain loop has nothing left to do. p1 is still at 1, meaning nums1[0] and nums1[1] (the 1 and 2) were never touched — they were already in their final resting places. Final result: [1, 2, 2, 3, 5, 6].
Notice how the largest value, 6, landed first, then 5, then 3, then 2 — the merged array assembled itself from the right edge inward.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Copy + sort | O((m+n) log(m+n)) | O(1) | ignores existing order, re-sorts everything |
| Front merge with shifting | O(m·n) | O(1) | each early insert shifts the tail right |
| Reverse three-pointer | O(m + n) | O(1) | one write per slot, no extra buffer |
Every one of the m + n slots is written exactly once, and each write does constant work, giving linear time. Because you reuse nums1's own trailing space instead of allocating a merged buffer, the extra space is O(1) — the whole reason the back-to-front direction exists.
Common mistakes
- Merging from the front. Comparing heads and writing to
nums1[0]overwrites a value you still need to read. Always fill from the back. - Forgetting the nums2 drain loop. If
nums2still has elements whennums1runs out (e.g.nums1 = [4, 5, 6, 0, 0, 0],nums2 = [1, 2, 3]), the leftovernums2values are the smallest and must be copied into the front. Skip the drain and they stay as zeros. - Writing a nums1 drain loop too. It's dead code. If
nums2empties first, remainingnums1values are already positioned correctly — copying them onto themselves is wasted work at best. - Using
<instead of>and clobbering ties. With<, equal tail values get pulled from the wrong side; harmless for plain integers but it breaks stability once elements carry extra data. - Confusing
mwithnums1.length.nums1.lengthism + n. Startp1atm - 1, the last real element — not at the last index of the array.
Where this pattern shows up next
The reverse-fill idea and its two-pointer cousins power a whole family of in-place array problems:
- Remove Duplicates from Sorted Array — a read/write pointer pair compacting a sorted array in place.
- Remove Element — the same overwrite-in-place mechanic, filtering a value out without extra space.
- Reverse String — two pointers converging from both ends, the simplest form of the technique.
- Best Time to Buy and Sell Stock — a single left-to-right scan tracking a running boundary, another O(n)/O(1) array sweep.
You can also step through Merge Sorted Array interactively to watch the three pointers walk right-to-left and the merged array fill from its back edge.
FAQ
Why do you merge from the back instead of the front?
Because nums1 is both an input and the output buffer. The smallest merged element belongs at index 0, which still holds a live value you haven't compared yet — writing there destroys data. The largest element belongs at the final index, which is guaranteed empty scratch space. Filling back-to-front means every write lands on a slot you no longer need, so nothing gets clobbered and no shifting is required.
What is the time and space complexity of Merge Sorted Array?
The reverse three-pointer solution runs in O(m + n) time and O(1) extra space. Each of the m + n destination slots is written exactly once with constant work per write, and the merge reuses nums1's own reserved trailing space instead of allocating a separate buffer. The copy-and-sort baseline, by contrast, is O((m + n) log(m + n)) because it re-sorts data that was already ordered.
Why is there no cleanup loop for nums1?
If nums2 runs out first, the remaining nums1 elements are already in their correct final positions — you'd only be copying them onto themselves. The only leftovers that need moving are from nums2, because when nums1 empties first, any un-placed nums2 values are the smallest and still sit in the wrong array. So a single while (p2 >= 0) drain loop is all the cleanup the algorithm needs.
What do m and n represent, and why not just use the array lengths?
m is the count of real elements in nums1 and n is the count in nums2. nums1.length equals m + n because its last n slots are zero-filled placeholders, not data. If you start the p1 pointer at nums1.length - 1 instead of m - 1, you begin on a zero placeholder and merge garbage into the result. Anchor p1 at m - 1 so it points at the genuine last value.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.