Merge Two Sorted Arrays

You are given two sorted arrays. Your task is to merge these two arrays into one sorted array, without using any built-in sorting functions. More formally, if the two arrays are \(A = [a_1, a_2, \dots, a_n]\) and \(B = [b_1, b_2, \dots, b_m]\) where each array is sorted in non-decreasing order, you must produce an array \(C\) such that:

\[ C = [c_1, c_2, \dots, c_{n+m}] \quad \text{with} \quad c_1 \le c_2 \le \cdots \le c_{n+m}, \]

Input/Output Format: The input is read from stdin and the output is written to stdout.

The merging should be achieved by a linear traversal of both arrays (i.e. using a two-pointer approach) ensuring an overall time complexity of \(O(n+m)\).

inputFormat

The input consists of four lines:

• The first line contains an integer \(n\) representing the number of elements in the first array.
• The second line contains \(n\) space-separated integers representing the first sorted array. If \(n = 0\), this line will be empty.
• The third line contains an integer \(m\) representing the number of elements in the second array.
• The fourth line contains \(m\) space-separated integers representing the second sorted array. If \(m = 0\), this line will be empty.

outputFormat

Output a single line containing \(n+m\) space-separated integers, the merged sorted array.

3
1 3 5
3
2 4 6

1 2 3 4 5 6