Merging lists of fragile objects Background: Chao Xu posted the following question some time ago: "Are there any known comparison sorting algorithms that do not reduce to sorting networks, such that each element is compared $O(\log n)$ times?". It seems that we are a bit stuck with the problem; I have discussed the same problem with Valentin Polishchuk in 2009, and we got nowhere.

To get some fresh ideas, I tried to come up with the simplest possible question that has a similar flavour and is not completely trivial. Hence the following question.



Question: You are given two sorted lists, each of them with $n$ elements. Can you merge the lists so that each element is only compared $O(1)$ times?

Naturally, the output should be a sorted list that contains all $2n$ elements.

[This turned out to be trivial, the answer is "no".]



Question 2: You are given two sorted lists, each of them with $n$ elements. Can you merge the lists so that each element is only compared $O(1)$ times, if you are allowed to discard a small fraction of elements?

More precisely, the output should be a sorted list that contains $2n-T(n)$ elements, and a "trashcan" that contains $T(n)$ elements. How small can you make the value $T(n)$? Getting $T(n) = n$ is trivial. Something like $T(n) = n/100$ should be doable in a straightforward manner. But can you get $T(n) = o(n)$?



Notes:


We use the comparison model here. Deterministic algorithms only, we are interested in the worst-case guarantees.
Note that both lists have exactly $n$ elements. If we had one list with $n$ elements and another with $1$ element, the answer is clearly "no"; however, if both lists are long, it seems that one might be able to do some "load balancing".
This time any kind of algorithm is valid. If your algorithm uses sorting networks as a building block, it is perfectly fine.
For a starting point, here is a simple algorithm that compares each element for at most 200 times: Just use the standard merge algorithm, but maintain counters for the heads of the lists. Once you reach 200, discard the element. Now for each element that you discard, you have successfully placed 200 elements in your output array. Hence you have achieved $T(n) = n/100$.
No, such an algorithm cannot exist.

Assume $t$ comparisons per element are allowed.

For a start, consider the situation of merging two lists, one of size
one, and the other of size $2^t$.
There are $2^t+1$ possible results, and an easy adversarial argument
shows that the element in the small list needs to participate in $t+1$ comparisons,
and this element has to go to the trash.

From this it is easy to construct an instance with two lists of size $n$
that consists of $n/2^t$ such small situations, and hence $n/2^t$ elements
have to go to the trash.

Hence, as long as $t$ is constant, it is impossible to have a trash of
$o(n)$.

On a side note, it seems that it is possible to match this bound by an algorithm where every element is compared with roughly log of the size of the surrounding part of the other list.  If this is of interest, I will try to work out the details.