# Selection algorithm on depth-$\text{O}(\log n)$ sorting network

Is there a sorting network of depth $\text{O}(\log n)$ for selecting the $i$th order statistic?

Remark: I've already asked a related question in a different context. Although the two questions are related, this is not a duplicate of the other one.

You can construct selection networks of depth O(log n) using graph expanders or using variants of the AKS sorting network.

S. Jimbo and A. Maruoka, A Method of Constructing Selection Networks with $O(\log n)$ Depth,SIAM J. Comput. 25, pp. 709-739, http://dx.doi.org/10.1137/S0097539793248329

• Jimbo and Maruoka only do median (as far as I can tell from the abstract+intro). However AKS/Paterson actually sort, so obviously can do selection too.
– Ari
May 28 '11 at 5:37
• It should be easy to reduce to median, by adding extra elements (and it can be done in parallel). Oct 16 '11 at 3:25