Merge Sorted Lists

You are given two sorted lists of integers. Your task is to merge these two lists into one new sorted list.

The process should be performed in linear time, i.e., in \(O(n+m)\) time, where \(n\) and \(m\) are the lengths of the two lists respectively.

This is a classic problem that tests your ability to merge two sorted arrays efficiently with a two-pointer technique.

inputFormat

The input is read from stdin and consists of four lines:

1. An integer \(n\), representing the number of elements in the first list.
2. A line with \(n\) space-separated integers (sorted in non-decreasing order) representing the first list.
3. An integer \(m\), representing the number of elements in the second list.
4. A line with \(m\) space-separated integers (sorted in non-decreasing order) representing the second list.

Note: If \(n\) or \(m\) is zero, the corresponding list will be empty (i.e. the line will be blank).

outputFormat

Output a single line to stdout containing the merged sorted list. The elements should be printed in non-decreasing order and separated by a single space. If the merged list is empty, output an empty line.

5
1 3 5 7 9
4
2 4 6 8

1 2 3 4 5 6 7 8 9