Merge Two Sorted Lists

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

The sorted linked lists are represented in the input as arrays. You need to merge these arrays while maintaining the sorted order.

Note: The solution should use \(O(n+m)\) time complexity where \(n\) and \(m\) are the lengths of the two lists.

For example, if the inputs are 1 3 5 and 2 4 6, then the merged output is 1 2 3 4 5 6.

inputFormat

The input is read from standard input (stdin) and is structured as follows:

1. An integer \(n\) representing the number of elements in the first sorted list.
2. \(n\) space-separated integers representing the first sorted list.
3. An integer \(m\) representing the number of elements in the second sorted list.
4. \(m\) space-separated integers representing the second sorted list.

If a list is empty, its count will be \(0\) and no elements will follow for that list.

outputFormat

The output should be printed to standard output (stdout) as a single line containing the merged sorted list. The integers should be separated by a single space. If both lists are empty, output nothing.

3
1 3 5
3
2 4 6

1 2 3 4 5 6