Practice: Sorted Union

Problem statement

The input consists of two lists in sorted order, and we must construct a new list to represent the reunion of the two lists. The reunion must maintain the sorted order. The two input lists must remain unchanged.

We can only traverse each list at most once. That is, the complexity should be $O(n)$. We can’t merge the two lists and then sort the result. We have to exploit the fact that the input lists are in sorted order.

For example, given the following:

list1 = [1, 3, 5, 10]
list2 = [0, 2, 6, 22, 23, 24, 25]

The reunion in sorted order is as follows:

reunion = [0, 1, 2, 3, 5, 6, 10, 22, 23, 24, 25]

We must solve this problem using local references.

Solution

We present a clever algorithm called intercalation to solve this problem. It can help us combine the two sorted lists ...