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.
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ en.wikipedia.org/wiki/Sorting_network#Optimal_sorting $\endgroup$– Jukka SuomelaMay 27, 2011 at 8:49
-
$\begingroup$ Well, well, who would've thunk it possible? (You can tell I'm not well versed in sorting networks.) Thanks. $\endgroup$– AriMay 28, 2011 at 5:39
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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$– AriMay 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