Merge Two Sorted Lists

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

The solution should efficiently merge the two lists using a two-pointer approach, achieving a time complexity of \(O(n + m)\), where \(n\) and \(m\) are the lengths of the two lists respectively.

Pay careful attention to cases where one or both lists may be empty and where duplicate elements might exist.

inputFormat

The input is given via standard input (stdin) and consists of three lines:

• The first line contains two integers \(n\) and \(m\) separated by a space, which represent the sizes of the first and second lists respectively.
• The second line contains \(n\) space-separated integers representing the first sorted list. If \(n = 0\), this line will be empty.
• The third line contains \(m\) space-separated integers representing the second sorted list. If \(m = 0\), this line will be empty.

outputFormat

Output the merged sorted list to standard output (stdout) as a sequence of integers separated by a space.

3 3
1 3 5
2 4 6

1 2 3 4 5 6