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

| cite | improve this answer | |
  • $\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 '11 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$ – Sasho Nikolov Oct 16 '11 at 3:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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