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

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

CC BY-SA 3.0
2011-05-28T05:37:48.947Z
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
CC BY-SA 3.0
2011-10-16T03:25:20.537Z
It should be easy to reduce to median, by adding extra elements (and it can be done in parallel).
Sasho Nikolov
CC BY-SA 3.0
2011-05-27T10:40:01.913Z
2011-05-27T10:40:01.913Z
Massimo Cafaro
<p>Is there a sorting network of depth $\text{O}(\log n)$ for selecting the $i$th order statistic?</p>

<p>Remark: I've already asked a related question in a <a href="https://cstheory.stackexchange.com/questions/6642/hans-on-log-log-n-time-linear-space-integer-sorting-algorithm">different context</a>.  Although the two questions are related, this is not a duplicate of the other one.</p>

CC BY-SA 3.0
2011-05-27T08:49:29.763Z
http://en.wikipedia.org/wiki/Sorting_network#Optimal_sorting
Jukka Suomela
CC BY-SA 3.0
2011-05-28T05:39:05.280Z
Well, well, who would've thunk it possible?  (You can tell I'm not well versed in sorting networks.)  Thanks.
Ari
<dc.parallel-comp><sorting><sorting-network>
Selection algorithm on depth-$\text{O}(\log n)$ sorting network
Ari
# Selection algorithm on depth-$\text{O}(\log n)$ sorting network

(Asked by: username_0 on 2011-05-27)

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](https://cstheory.stackexchange.com/questions/6642/hans-on-log-log-n-time-linear-space-integer-sorting-algorithm). Although the two questions are related, this is not a duplicate of the other one.

**Tags:** dc.parallel-comp, sorting, sorting-network
> **Comments:**
> **username_1**: http://en.wikipedia.org/wiki/Sorting_network#Optimal_sorting  
> **username_0**: Well, well, who would've thunk it possible?  (You can tell I'm not well versed in sorting networks.)  Thanks.  

---

## 1 answers

### Answer by username_2 on 2011-05-27. Score: 5 | Accepted answer

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>

> **Comments:**
> **username_0**: 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.  
> **username_3**: It should be easy to reduce to median, by adding extra elements (and it can be done in parallel).  

---

