<p>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 (<a href="https://en.wikipedia.org/wiki/Sorting_network#Constructing_sorting_networks" rel="nofollow noreferrer">according to Wikipedia</a>).</p>

CC BY-SA 3.0
2017-05-16T09:36:34.057Z
2017-05-16T09:36:34.057Z
xavierm02
<p>Given $n$ distinct elements.</p>

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

<p>Or is there a higher lower bound?</p>

CC BY-SA 3.0
2017-05-12T13:38:12.673Z
You can get $O((\log n)^2)$ using a [sorting network](https://en.wikipedia.org/wiki/Sorting_network#Constructing_sorting_networks), or even $O(\log n)$ with a huge constant according to Wikipedia.
xavierm02
CC BY-SA 3.0
2017-05-12T16:21:04.267Z
$O(\lg^2 n )$ is easy to obtain with just simple merge sort.
Okay ty for the answer
Vk1
CC BY-SA 3.0
2017-05-13T17:10:46.937Z
@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
CC BY-SA 3.0
2017-05-15T12:11:10.793Z
@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
CC BY-SA 3.0
2017-05-16T10:01:42.057Z
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
CC BY-SA 3.0
2017-05-16T13:48:28.847Z
@EmilJeřábek:- Thank you so much for the reference...
This was the answer i was looking for.

Thanks a lot.
Vk1
<ds.algorithms><sorting>
Necessary and sufficient number of comparisons by every element to fully sort a set of n elements?
Vk1
# Necessary and sufficient number of comparisons by every element to fully sort a set of n elements?

(Asked by: username_0 on 2017-05-12)

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?

**Tags:** ds.algorithms, sorting

> **Comments:**
> **username_1**: You can get $O((\log n)^2)$ using a [sorting network](https://en.wikipedia.org/wiki/Sorting_network#Constructing_sorting_networks), or even $O(\log n)$ with a huge constant according to Wikipedia.  
> **username_0**: $O(\lg^2 n )$ is easy to obtain with just simple merge sort. Okay ty for the answer  
> **username_2**: @username_1 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")  
> **username_1**: @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).  
> **username_3**: 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 .  
> **username_0**: @EmilJeřábek:- Thank you so much for the reference... This was the answer i was looking for.  Thanks a lot.  

---

## 1 answers

### Answer by username_1 on 2017-05-16. Score: 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](https://en.wikipedia.org/wiki/Sorting_network#Constructing_sorting_networks)).


---

