20
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 8
    $\begingroup$ You said that "If we had one list with n elements and another with 1 element, the answer is clearly no." Isn't the case with n elements in each list a more general problem? For example, if we're promised that all the elements in the second list except the first element are much larger than the all the elements in the first list, doesn't this reduce to the first problem? $\endgroup$
    – Robin Kothari
    Commented Sep 3, 2011 at 22:44
  • $\begingroup$ @Robin: Right, so I failed to come up with a non-trivial question, thanks. Your observation seems to give an $\Omega(\log n)$ lower bound if we insist on having all elements sorted. Let me slightly augment the question... $\endgroup$
    – Jukka Suomela
    Commented Sep 3, 2011 at 22:56
  • $\begingroup$ And in case someone wonders what is the point of the seemingly strange definition in Question 2: if we can make $T(n)$ very small, perhaps we could use something like merge sort to almost solve the original problem, and worry about a tiny fraction of elements in the trashcan later. $\endgroup$
    – Jukka Suomela
    Commented Sep 3, 2011 at 23:07

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.