Merge Sorted Arrays

You are given two arrays that are sorted in non-decreasing order. Your task is to merge these two arrays into a single sorted array.

The procedure should be efficient by using a two-pointer method, achieving a time complexity of \(O(n+m)\) where \(n\) and \(m\) are the lengths of the two arrays respectively.

inputFormat

The input is given via stdin with the following format:

1. The first line contains an integer \(n\), the number of elements in the first array.
2. The second line contains \(n\) space-separated integers in non-decreasing order.
3. The third line contains an integer \(m\), the number of elements in the second array.
4. The fourth line contains \(m\) space-separated integers in non-decreasing order.

outputFormat

Output a single line to stdout containing the merged sorted array. The numbers should be space-separated.

3
1 3 5
3
2 4 6

1 2 3 4 5 6