An optimally efficient selection algorithm
Richard Cole · Information Processing Letters · 1988
We give an optimally efficient parallel algorithm for selection on the EREW PRAM. It requires a linear number of operations and O(log n log∗n) time. A modification of the algorithm runs on the CRCW PRAM. It requires a linear number of operations and O(log n log∗/log log n) time.