An optimal hardware-algorithm for selection using a fixed-size parallel classifier device

We present a hardware-algorithm for selecting the ?-th smallest item among N elements (for all ranges of N) using a p-classifier device, while strictly enforcing conflict-free memory accesses. Specifically, we show that, by using our design, selection can be accomplished optimally in O(N/p) time. © 1999 Springer-Verlag Berlin Heidelberg.