up vote 39 down vote favorite
12

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. (iirc, this was first presented by Rob Johnson at Stony Brook's algorithm seminar).

share|cite|improve this question
  • 2
    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? – Jeremy Jun 27 '11 at 11:46
  • 4
    @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 Jun 27 '11 at 13:06
  • 6
    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 reddit.com/comments/9jqsi/… – Chao Xu Jul 4 '11 at 18:11
  • 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. – Jeremy Jul 4 '11 at 20:15
  • 2
    Now there is a new related (but hopefully much easier) question: cstheory.stackexchange.com/questions/8073/… – Jukka Suomela Sep 3 '11 at 22:03
up vote 17 down vote accepted

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

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

share|cite|improve this answer
  • We would like to know who you are! :D – Tayfun Pay Nov 3 '12 at 19:58
  • @someone is Sergio Cabello – someone Nov 20 '12 at 16:11

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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