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.
Asked
Active
Viewed 263 times
1
-
1http://en.wikipedia.org/wiki/Sorting_network#Optimal_sorting – Jukka Suomela May 27 '11 at 08:49
-
Well, well, who would've thunk it possible? (You can tell I'm not well versed in sorting networks.) Thanks. – Ari May 28 '11 at 05:39
1 Answers
5
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
Massimo Cafaro
- 2,216
- 20
- 19
-
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 05:37
-
1It should be easy to reduce to median, by adding extra elements (and it can be done in parallel). – Sasho Nikolov Oct 16 '11 at 03:25