3

Given $n$ distinct elements.

Is there a sorting algorithm which ensures that every element is compared atmost $\lg n$ time?

Or is there a higher lower bound?

Vk1
  • 137
  • 9
  • 4
    You can get $O((\log n)^2)$ using a sorting network, or even $O(\log n)$ with a huge constant according to Wikipedia. – xavierm02 May 12 '17 at 13:38
  • 1
    $O(\lg^2 n )$ is easy to obtain with just simple merge sort. Okay ty for the answer – Vk1 May 12 '17 at 16:21
  • 3
    @xavierm02 the log-depth sorting network seems to completely answer the question; please post as an answer! (even though it's available on Wikipedia, the OP obviously didn't know to search for the term "sorting network") – Joshua Grochow May 13 '17 at 17:10
  • @user13857 I'm having trouble seeing how one would prove that merge sort gives $O(\log^2 n)$. It feels like some element could be compared to half of the array (if when merging the two halves, all elements on the right are bigger than all elements on the left, then the first element on the right will be compared to all elements on the left). – xavierm02 May 15 '17 at 12:11
  • 2
    A different $O(\log n)$ algorithm is given in the answer to https://cstheory.stackexchange.com/questions/7131/sorting-algorithm-such-that-each-element-is-compared-o-log-n-times-and-doe . – Emil Jeřábek May 16 '17 at 10:01
  • @EmilJeřábek:- Thank you so much for the reference... This was the answer i was looking for.

    Thanks a lot.

     – Vk1 May 16 '17 at 13:48

1 Answers1

3

Note that in a sorting network, the number of times an element is compared is bounded by the depth of the network. There are several simple sorting networks of depth $O((\log n)^2)$. The AKS network has a depth of $O(\log n)$ with a huge constant (according to Wikipedia).

xavierm02
  • 556
  • 3
  • 11