3
$\begingroup$

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?

$\endgroup$
6
  • 4
    $\begingroup$ You can get $O((\log n)^2)$ using a sorting network, or even $O(\log n)$ with a huge constant according to Wikipedia. $\endgroup$
    – xavierm02
    Commented May 12, 2017 at 13:38
  • 1
    $\begingroup$ $O(\lg^2 n )$ is easy to obtain with just simple merge sort. Okay ty for the answer $\endgroup$
    – Vk1
    Commented May 12, 2017 at 16:21
  • 3
    $\begingroup$ @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") $\endgroup$ Commented May 13, 2017 at 17:10
  • $\begingroup$ @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). $\endgroup$
    – xavierm02
    Commented May 15, 2017 at 12:11
  • 2
    $\begingroup$ A different $O(\log n)$ algorithm is given in the answer to cstheory.stackexchange.com/questions/7131/… . $\endgroup$ Commented May 16, 2017 at 10:01

1 Answer 1

3
$\begingroup$

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

$\endgroup$

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