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 in an efficient way, $O(n)$.

The basic idea behind the algorithm is that the minimum elements are at the beginning of list1 and list2 in sorted lists. Therefore, only these two (1 and 0) elements are a candidate to be the first element inside the resulting list.

We pick the smaller element between the two, 0, and add it to the resulting list. We picked an element from list2, so we iterate to the right inside list2.

We repeat this process on the new lists list1 = [1, 3, 5, 10] and list2 = [2, 6, 22, 23, 24, 25] (notice we ignore the 0 in list2 since we already used it). We repeat the process until the lists run out of elements. Now, there are a few possibilities:

• If the lists have the same size, they’ll run out of elements concomitantly. If so, we finished since we added all elements.
• The first list, list1, runs out of elements, which means that list2 is longer and all the remaining elements in list2 are bigger than the previously added elements. We add all the elements remaining in list2 to the resulting list.
• The second list, list2, runs out of elements, which means that list1 is longer and all the remaining elements in list1 are bigger than the previously added elements. We add all the elements remaining in list1 to the resulting list.

From the description of the algorithm, we can see that it respects our constraint of iterating over a list only once, and the overall complexity is $O(n)$. We’ll indeed have three while loops, but they aren’t nested. The loops will only process an element once.

The first loop does the intercalation, and the last two loops add the remaining elements in case one of the lists is longer. They only process elements unprocessed by the first loop.

See the animations: