Problem

The merging procedure is an essential part of “Merge Sort” (which is considered in one of the next problems).

Given: A positive integer $n \le 10^5$ and a sorted array $A[1..n]$ of integers from $-10^5$ to $10^5$, a positive integer $m \le 10^5$ and a sorted array $B[1..m]$ of integers from $-10^5$ to $10^5$.

Return: A sorted array $C[1..n+m]$ containing all the elements of $A$ and $B$.

Sample Dataset

4
2 4 10 18
3
-5 11 12

Sample Output

-5 2 4 10 11 12 18

Hintclick to expand

The very first element of $C$ is either $A[1]$ or $B[1]$, whichever is smaller. The rest of $C$ can then be constructed recursively.

Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006.