Merge Two Sorted Lists

Problem Statement

You are given two sorted lists. Your task is to merge these two lists into a single sorted list without modifying the original lists. The expected merge must be achieved using a two-pointer technique.

Note: If one of the lists is empty, the output should simply be the other list.

The merging process can be understood as follows: Given two sorted sequences \(A = [a_1, a_2, \dots, a_n]\) and \(B = [b_1, b_2, \dots, b_m]\), produce a sorted sequence \(C\) that contains all the elements of \(A\) and \(B\).

inputFormat

The input consists of four lines:

1. The first line contains an integer \(n\), the number of elements in the first list.
2. The second line contains \(n\) space-separated integers in sorted order. If \(n = 0\), this line will be empty.
3. The third line contains an integer \(m\), the number of elements in the second list.
4. The fourth line contains \(m\) space-separated integers in sorted order. If \(m = 0\), this line will be empty.

outputFormat

Output the merged sorted list on a single line. The numbers should be space-separated.

3
1 3 5
3
2 4 6

1 2 3 4 5 6