39
$\begingroup$

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

Improve this question
$\endgroup$
14
  • 2
    $\begingroup$ 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? $\endgroup$
    – Jeremy
    Jun 27 '11 at 11:46
  • 5
    $\begingroup$ @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. $\endgroup$
    – Jukka Suomela
    Jun 27 '11 at 13:06
  • 6
    $\begingroup$ 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/… $\endgroup$
    – Chao Xu
    Jul 4 '11 at 18:11
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jeremy
    Jul 4 '11 at 20:15
  • 2
    $\begingroup$ Now there is a new related (but hopefully much easier) question: cstheory.stackexchange.com/questions/8073/… $\endgroup$
    – Jukka Suomela
    Sep 3 '11 at 22:03
17
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ We would like to know who you are! :D $\endgroup$
    – Tayfun Pay
    Nov 3 '12 at 19:58
  • $\begingroup$ @someone is Sergio Cabello $\endgroup$
    – someone
    Nov 20 '12 at 16:11
  • $\begingroup$ @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? $\endgroup$
    – Vk1
    Oct 5 '19 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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