<p>Upon discussing this with Michael T. Goodrich, it seems that the parallel sorting algorithm by Cole for EREW PRAM does the job. See</p>

<ul>
<li>Richard Cole: "<a href="http://dx.doi.org/10.1137/0222081">Parallel Merge Sort</a>". SIAM J. Comput. 17(4): 770-785 (1988).</li>
</ul>

<p>In that algorithm there are $O(\log n)$ rounds and in each round each element participates in $O(1)$ comparisons. (One has to understand the algorithm to see that we do not abuse of making copies of each element.)</p>

<p>An extension of that algorithm for parallel pointer machine is given in </p>

<ul>
<li>M.T. Goodrich, S.R. Kosaraju: "<a href="http://dx.doi.org/10.1145/226643.226670">Sorting on a Parallel Pointer Machine with Applications to Set Expression Evaluation</a>". J. ACM 43(2): 331-361 (1996). </li>
</ul>

CC BY-SA 3.0
2012-11-03T19:58:12.370Z
We would like to know who you are! :D
Tayfun Pay
CC BY-SA 3.0
2012-11-20T16:11:47.280Z
@someone is Sergio Cabello
someone
CC BY-SA 4.0
2019-10-05T17:16:42.613Z
@someone. Ty for this answer. It mentions the results in EREW model. Since its Exclusive read and exclusive write model, it means that all the locations are touched at most O(1) time in each round and thus $O(\log n)$ times on the whole.

Does this imply a straightforward algorithm for finding median in RAM (or even EREW model) using $O(\log n)$ comparisons per element?
Vk1
CC BY-SA 3.0
2012-10-31T03:51:32.953Z
2012-11-01T21:02:59.983Z
2012-11-01T21:02:59.983Z
someone
<p>Are there any known comparison sorting algorithms that do not reduce to sorting networks, such that each element is compared $O(\log n)$ times?</p>

<p>As far as I know, the only way to sort with $O(\log n)$ comparison on each element is to construct an AKS sorting network for $n$ inputs, and run the input on the sorting network.</p>

<p>AKS is not easy to implement and has an impractical constant factor, so there are motivations to search for other algorithms.</p>

<p>An algorithm with $O(\log^2 n)$ comparisons per item which does not seem to imply a sorting network is presented <a href="http://www.reddit.com/comments/9jqsi/how_to_merge_sorted_lists_with_olog_n_comparisons/">here</a>. (iirc, this was first presented by <a href="http://www.cs.sunysb.edu/~rob/">Rob Johnson</a> at Stony Brook's algorithm seminar).</p>

CC BY-SA 3.0
2011-06-26T23:25:08.433Z
Updated, I should have said I'm looking for algorithms that doesn't reduce to a sorting network.
Chao Xu
CC BY-SA 3.0
2011-06-27T11:46:42.530Z
I don't understand the question: many sequential algorithms seems to correspond to your request. e.g. Merge sort is a classical sorting algorithm, and does not make more than $\log n$ comparison per element. Maybe you are asking about *parallel* sorting algorithms?
J.y B.y
CC BY-SA 3.0
2011-06-27T13:06:35.220Z
@Jeremy: If you merge two lists, $(a_1, ..., a_n)$ and $(b_1, ..., b_n)$, you may end up comparing $a_1$ against each of $b_1, ..., b_n$, that is, $\Omega(n)$ comparisons per one element. And this was just one "merge" step. Of course the *average* number of comparisons is necessarily small, but the question is about the *worst-case* complexity.
Jukka Suomela
CC BY-SA 3.0
2011-07-04T16:52:11.230Z
I wonder what is the connection between this question and sorting networks. Of course a sorting network is a solution to the problem, but what about the converse case? Could we have a solution to this problem *without* implicitly designing a good sorting network?
Jukka Suomela
CC BY-SA 3.0
2011-07-04T18:11:49.087Z
I believe that's possible. Sorting networks are data oblivious and have predetermined way of comparisons, but a sorting algorithm might be able to choose between different set of operations depend on the data. One can modify merge sort into a algorithm with $O(\log^2 n)$ comparison for each element, and doesn't seem to imply a sorting network http://www.reddit.com/comments/9jqsi/how_to_merge_sorted_lists_with_olog_n_comparisons/
Chao Xu
CC BY-SA 3.0
2011-07-04T20:15:07.397Z
Jukka: Thanks, I get your point. 
But that's just when using naive merging: one can merge $(a_1,\ldots,a_n)$ with $(b_1,\ldots,b_n)$ using doubling search to place each element, which is still $n$ comparisons in total in the worst case, but $\lg n$ comparisons per element at maximum, which yields the version of merge sort alluded to by Chao.
J.y B.y
CC BY-SA 3.0
2011-07-05T00:46:58.937Z
@Chao: That is a beautiful algorithm!  I think that you should add the statement of the result (an algorithm with O(log^2) comparisons per item which does not seem to imply a sorting network) and the link to the question.
Tsuyoshi Ito
CC BY-SA 3.0
2011-07-05T06:21:38.083Z
I think that these algorithms are hard to obtain. For a slightly related problem, see proposition 1 on page 10 here:
http://arxiv.org/PS_cache/arxiv/pdf/1002/1002.0562v1.pdf
domotorp
CC BY-SA 3.0
2011-07-05T15:51:54.643Z
is there a precise way to define "does not reduce to a sorting network"?
Sasho Nikolov
CC BY-SA 3.0
2011-07-05T22:19:35.587Z
@Sasho: I doubt there is.  But the algorithm with O(log^2) comparisons per item described in the linked page gives you an idea of what it intuitively means.
Tsuyoshi Ito
CC BY-SA 3.0
2011-07-05T23:34:24.990Z
Is randomized algorithm acceptable? My randomized PRAM algorithms are rusty, but I remember there is a relatively simple randomized algorithm achieving O(log n) on a parallel computer. In any case, it is not hard to come up with an algorithm that would compare every element $O(\log n)$ times with high probability. I can give details if there is interest.
Sariel Har-Peled
CC BY-SA 3.0
2011-07-06T00:12:06.423Z
I wonder what would happen if one tried to use the following strategy: Maintain a counter with each element, keeping track of the number of comparisons. Then take a reasonable sorting algorithm, e.g., merge sort; run it as usual but if at some point you encounter an element that has already been compared too many times ($C \log n$ for a large constant $C$), then move it to the "waiting room". In the end, the list is sorted, except that we have some elements in the waiting room that still need to be sorted & merged. Recursively sort the waiting room & merge. What would be a worst-case input?
Jukka Suomela
CC BY-SA 3.0
2011-07-06T00:48:04.257Z
@Sariel: I'm only interested in deterministic algorithm(like you said, $O(log n)$ with high probability is not hard to come up with).
Chao Xu
CC BY-SA 3.0
2011-09-03T22:03:08.593Z
Now there is a new related (but hopefully much easier) question: http://cstheory.stackexchange.com/questions/8073/merging-lists-of-fragile-objects
Jukka Suomela
<ds.algorithms><sorting><sorting-network>
Sorting algorithm, such that each element is compared $O(\log n)$ times, and doesn't depend on a sorting network
Chao Xu
# Sorting algorithm, such that each element is compared $O(\log n)$ times, and doesn't depend on a sorting network

(Asked by: username_0 on 2011-06-26)

Are there any known comparison sorting algorithms that do not reduce to sorting networks, such that each element is compared $O(\log n)$ times?

As far as I know, the only way to sort with $O(\log n)$ comparison on each element is to construct an AKS sorting network for $n$ inputs, and run the input on the sorting network.

AKS is not easy to implement and has an impractical constant factor, so there are motivations to search for other algorithms.

An algorithm with $O(\log^2 n)$ comparisons per item which does not seem to imply a sorting network is presented [here](http://www.reddit.com/comments/9jqsi/how_to_merge_sorted_lists_with_olog_n_comparisons/). (iirc, this was first presented by [Rob Johnson](http://www.cs.sunysb.edu/~rob/) at Stony Brook's algorithm seminar).

**Tags:** ds.algorithms, sorting, sorting-network
> **Comments:**
> **username_0**: Updated, I should have said I'm looking for algorithms that doesn't reduce to a sorting network.  
> **username_1**: I don't understand the question: many sequential algorithms seems to correspond to your request. e.g. Merge sort is a classical sorting algorithm, and does not make more than $\log n$ comparison per element. Maybe you are asking about *parallel* sorting algorithms?  
> **username_2**: @Jeremy: If you merge two lists, $(a_1, ..., a_n)$ and $(b_1, ..., b_n)$, you may end up comparing $a_1$ against each of $b_1, ..., b_n$, that is, $\Omega(n)$ comparisons per one element. And this was just one "merge" step. Of course the *average* number of comparisons is necessarily small, but the question is about the *worst-case* complexity.  
> **username_2**: I wonder what is the connection between this question and sorting networks. Of course a sorting network is a solution to the problem, but what about the converse case? Could we have a solution to this problem *without* implicitly designing a good sorting network?  
> **username_0**: I believe that's possible. Sorting networks are data oblivious and have predetermined way of comparisons, but a sorting algorithm might be able to choose between different set of operations depend on the data. One can modify merge sort into a algorithm with $O(\log^2 n)$ comparison for each element, and doesn't seem to imply a sorting network http://www.reddit.com/comments/9jqsi/how_to_merge_sorted_lists_with_olog_n_comparisons/  
> **username_1**: Jukka: Thanks, I get your point.  But that's just when using naive merging: one can merge $(a_1,\ldots,a_n)$ with $(b_1,\ldots,b_n)$ using doubling search to place each element, which is still $n$ comparisons in total in the worst case, but $\lg n$ comparisons per element at maximum, which yields the version of merge sort alluded to by Chao.  
> **username_3**: @Chao: That is a beautiful algorithm!  I think that you should add the statement of the result (an algorithm with O(log^2) comparisons per item which does not seem to imply a sorting network) and the link to the question.  
> **username_4**: I think that these algorithms are hard to obtain. For a slightly related problem, see proposition 1 on page 10 here: http://arxiv.org/PS_cache/arxiv/pdf/1002/1002.0562v1.pdf  
> **username_5**: is there a precise way to define "does not reduce to a sorting network"?  
> **username_3**: @Sasho: I doubt there is.  But the algorithm with O(log^2) comparisons per item described in the linked page gives you an idea of what it intuitively means.  
> **username_6**: Is randomized algorithm acceptable? My randomized PRAM algorithms are rusty, but I remember there is a relatively simple randomized algorithm achieving O(log n) on a parallel computer. In any case, it is not hard to come up with an algorithm that would compare every element $O(\log n)$ times with high probability. I can give details if there is interest.  
> **username_2**: I wonder what would happen if one tried to use the following strategy: Maintain a counter with each element, keeping track of the number of comparisons. Then take a reasonable sorting algorithm, e.g., merge sort; run it as usual but if at some point you encounter an element that has already been compared too many times ($C \log n$ for a large constant $C$), then move it to the "waiting room". In the end, the list is sorted, except that we have some elements in the waiting room that still need to be sorted & merged. Recursively sort the waiting room & merge. What would be a worst-case input?  
> **username_0**: @Sariel: I'm only interested in deterministic algorithm(like you said, $O(log n)$ with high probability is not hard to come up with).  
> **username_2**: Now there is a new related (but hopefully much easier) question: http://cstheory.stackexchange.com/questions/8073/merging-lists-of-fragile-objects  

---

## 1 answers

### Answer by username_7 on 2012-10-31. Score: 17 | Accepted answer

Upon discussing this with Michael T. Goodrich, it seems that the parallel sorting algorithm by Cole for EREW PRAM does the job. See

* Richard Cole: "[Parallel Merge Sort](http://dx.doi.org/10.1137/0222081)". SIAM J. Comput. 17(4): 770-785 (1988).

In that algorithm there are $O(\log n)$ rounds and in each round each element participates in $O(1)$ comparisons. (One has to understand the algorithm to see that we do not abuse of making copies of each element.)

An extension of that algorithm for parallel pointer machine is given in

* M.T. Goodrich, S.R. Kosaraju: "[Sorting on a Parallel Pointer Machine with Applications to Set Expression Evaluation](http://dx.doi.org/10.1145/226643.226670)". J. ACM 43(2): 331-361 (1996).

> **Comments:**
> **username_8**: We would like to know who you are! :D  
> **username_7**: @someone is Sergio Cabello  
> **username_9**: @someone. Ty for this answer. It mentions the results in EREW model. Since its Exclusive read and exclusive write model, it means that all the locations are touched at most O(1) time in each round and thus $O(\log n)$ times on the whole.  Does this imply a straightforward algorithm for finding median in RAM (or even EREW model) using $O(\log n)$ comparisons per element?  

---

