TWO SELECTION ALGORITHMS ON A MESH-CONNECTED COMPUTER
Bogdan S. Chlebus · Parallel Processing Letters · 1992
Two deterministic selection algorithms on an n × n mesh-connected processor array are developed. The model of computation is restricted in the following sense: at every step each processor buffers exactly one of the original keys, and every one of the original keys is buffered by a processor. The first algorithm operates in time 2.5n + o(n). It is a general selection algorithm, that is, its complexity bound does not depend on the rank of the element searched for. The second algorithm has its time bound depending on the rank of the item sought. This bound is [Formula: see text], where the rank is x2n2. This algorithm is superior to the previous one for approximately 10% of the smallest and 10% of the largest keys.