We have an array of size m+n in which m elements are present, in sorted order, and a second array of size n, again in sorted order. We want both of them to be sorted and present in the first array. No third array is supposed to be given.
Example:
1, 3, 55, 66, 77, _, _, _
5, 9, 20
The answer would be:
1, 3, 5, 9, 20, 55, 66, 77
Do a regular merge sort but in reverse comparing the largest numbers first, storing (reversed) into the end of the first array going backwards. This way, the elements you're merging are never overwritten (that this works is easy to see if you think about it for a moment).
// merge the elements in B[] to A[], starting from the last one
void merge(int A[], int m, int B[], int n) {
// m-1 and n-1 represent the current element index in A[] and B[] respectively
while (n > 0) { // there are still elements in B[] not merged
if (m > 0 && A[m-1] > B[n-1]) { // current element in A[] > current element in B[]
A[m+n-1] = A[m-1]; // move current element of A[] to its right position
--m; // decrease current element index of A[]
}
else { // current element in A[] <= current element in B[]
A[m+n-1] = B[n-1]; // move current element in B[] to its right position
--n; // decrease current element index of B[]
}
}
}
In-place basically requires we only use "constant" amount of memory, which does not change with different input array sizes. However, the question itself allocate extra amount of memory that is the same to the size of one of the two input arrays, which is O(n) memory in worst case. This basically makes the idea of "in-place" meaningless...
The question might be better phrased as "merge without extra memory", which is a more precise description of its real intention...
Move the contents of the first array to the end of the first array, such that the empty elements are now at the beginning. Then merge the two sequences as usual into the first array.
