Fast Deterministic Selection on a Mesh-Connected Processor Array

We present a deterministic algorithm for selecting the element of rank k among N = n2 elements, 1 ≤ k ≤ N, on an n X n mesh-connected processor array in (1.44 + Є)n parallel computation steps, for any constant Є > 0, using constant sized queues. This is a considerable improvement over the best previous deterministic algorithm, which was based upon sorting and required 3n steps. Our algorithm can be generalized to solve the problem of selection on higher dimensional meshes, achieving time bounds better than the known results in each case