Merge two sorted array A and B, where A has larger buffer to hold B at the end of it.

Problem

You are given two sorted arrays, A and B, where A has a large enough buffer at the end to hold B. Write the algorithm to merge A and B without allocation additional memory.

Answer

Merging integers backward,  $O(N)$

Given the fact that array A has free space at the end to hold array B. (See Figure 1.)

It is similar to the merge step of the Merge sort except for the fact that we are merging the array B into A.

The running time of this algorithm is $O(N)$.

Here is the complete code in C++.

Python solution

Practice statistics

13:51: to write up the code

02:43: to verify the code.

03:00: to check for the typos

UPDATE(2022-06-13): Solved the problem again, the algorithm was sound but had a minor bug.

 Original answers put the merged values from the end of the larger buffer and can leave the duplicate values in front of the larger buffer if the empty space of the buffer is larger than the smaller buffer.  This solution correctly put the merged values in the right position such that the merged values start from zero of the larger buffer.