Merge Two Sorted Arrays In Place

You are given two arrays, A of length m and B of length n, both sorted in non-decreasing order. Array A has exactly m + n total slots: the first m hold its actual elements and the remaining n slots are unused placeholder space reserved for the merge. Merge B into A in place so that A becomes a single sorted array of length m + n containing all m + n values, filling from the back so that unread elements of A are never overwritten before they're used.

Input: The first line contains two space-separated integers m and n - the number of real elements in A and B respectively. The second line contains the m real elements of A in non-decreasing order (empty if m = 0). The third line contains the n elements of B in non-decreasing order (empty if n = 0). Output: Print the merged array of m + n integers in non-decreasing order, space-separated, on a single line.

0 <= m, n <= 10^5 1 <= m + n <= 10^5 -10^9 <= A[i], B[i] <= 10^9

This is a clever adaptation of the standard two-pointer merge technique, reversed in direction specifically to exploit WHERE the extra space is located (at the end) - a good example of adapting a familiar technique's direction based on a problem's specific memory-layout constraint.

Merge two sorted arrays into one, using the extra empty space already available at the end of the first array. Brute force: Copy both arrays' real elements into a separate temporary array, merge them there, then copy the result back into A - this works but uses O(m+n) extra space, when the reserved empty slots in A already provide enough room to merge in place. Optimised: Filling from the BACK (largest values first) is exactly what avoids ever overwriting an element of A that hasn't been read yet - since the empty slots are at the END of A, working backward ensures every 'real' value of A is compared and placed BEFORE the slot it currently occupies gets overwritten by the merge.

1. Since A has extra room at the END, work BACKWARDS: compare the LAST real elements of A and B, and place the LARGER one in the last empty slot. 2. Move the two SOURCE pointers (one for A's real elements, one for B) LEFTWARD, and a DESTINATION pointer for the next slot to fill, also moving leftward. 3. If A still has elements left once B is exhausted, they're already correctly placed; if B still has elements left once A is exhausted, copy them directly.

Time: O(m + n) - a single combined backward pass through both arrays. Space: O(1) extra space - the merge happens directly within A's existing reserved slots.

Handle m = 0 (the output is exactly B) and n = 0 (the output is exactly A); the merge must run in O(m + n) time by filling positions from the back, without extra arrays or re-sorting, even at m + n = 10^5.

Be ready to explain explicitly WHY merging from the FRONT (like a standard merge) would NOT work safely here - it would overwrite elements of A that the merge process still needs to read later, which working from the BACK entirely avoids.