<p>No, such an algorithm cannot exist.</p>

<p>Assume $t$ comparisons per element are allowed.</p>

<p>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.</p>

<p>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.</p>

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

<p>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.</p>

CC BY-SA 3.0
2013-11-28T14:02:42.953Z
2013-12-01T16:59:27.550Z
2013-12-01T16:59:27.550Z
Riko Jacob
<p><strong>Background:</strong> Chao Xu posted the following question some time ago: "<a href="https://cstheory.stackexchange.com/questions/7131/sorting-algorithm-such-that-each-element-is-compared-o-log-n-times-and-does">Are there any known comparison sorting algorithms that do not reduce to sorting networks, such that each element is compared $O(\log n)$ times?</a>". 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.</p>

<p>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.</p>

<hr>

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

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

<p>[This turned out to be trivial, the answer is "no".]</p>

<hr>

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

<p>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)$?</p>

<hr>

<p><strong>Notes:</strong></p>

<ul>
<li><p>We use the comparison model here. Deterministic algorithms only, we are interested in the worst-case guarantees.</p></li>
<li><p>Note that <em>both</em> 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 <em>might</em> be able to do some "load balancing".</p></li>
<li><p>This time any kind of algorithm is valid. If your algorithm uses sorting networks as a building block, it is perfectly fine.</p></li>
<li><p>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$.</p></li>
</ul>

CC BY-SA 3.0
2011-09-03T22:44:39.127Z
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?
Robin Kothari
CC BY-SA 3.0
2011-09-03T22:56:56.247Z
@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...
Jukka Suomela
CC BY-SA 3.0
2011-09-03T23:07:12.640Z
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.
Jukka Suomela
<ds.algorithms><sorting><sorting-network>
Merging lists of fragile objects
Jukka Suomela
# Merging lists of fragile objects

(Asked by: username_0 on 2011-09-03)

**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?](https://cstheory.stackexchange.com/questions/7131/sorting-algorithm-such-that-each-element-is-compared-o-log-n-times-and-does)". 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$.

**Tags:** ds.algorithms, sorting, sorting-network
> **Comments:**
> **username_1**: 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?  
> **username_0**: @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...  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_2 on 2013-11-28. Score: 5 | Accepted answer

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.


---

