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