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.


1 Answer 1


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

  • $\begingroup$ 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. $\endgroup$
    – Ari
    May 28, 2011 at 5:37
  • 1
    $\begingroup$ It should be easy to reduce to median, by adding extra elements (and it can be done in parallel). $\endgroup$ Oct 16, 2011 at 3:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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