# Necessary and sufficient number of comparisons by every element to fully sort a set of n elements? [duplicate]

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?

## marked as duplicate by D.W., Kaveh, David Eppstein, Jan Johannsen, András SalamonMay 18 '17 at 12:51

• 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
• $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
• @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
• A different $O(\log n)$ algorithm is given in the answer to cstheory.stackexchange.com/questions/7131/… . – Emil Jeřábek supports Monica May 16 '17 at 10:01
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).