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)$?
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$.