Merge Two Sorted Lists

You are given two sorted lists of integers. Your task is to merge the two lists into a single sorted list without using built-in sorting functions. The expected time complexity is \(O(n+m)\), where \(n\) and \(m\) are the lengths of the two lists.

The input is provided via standard input (stdin) and the resultant merged list should be output via standard output (stdout) as a space-separated list of integers.

For example, merging the lists [1, 3, 5] and [2, 4, 6] should yield [1, 2, 3, 4, 5, 6].

inputFormat

The input consists of two lines read from stdin:

• The first line contains a sorted list of integers separated by spaces. If the list is empty, the line will be empty.
• The second line contains another sorted list of integers separated by spaces. If the list is empty, the line will be empty.

Note: The numbers may be negative and the lists can be of different lengths.

outputFormat

Output a single line containing the merged sorted list of integers, separated by spaces.

1 3 5
2 4 6

1 2 3 4 5 6