Optimal algorithms for selection on a mesh-connected processor array

The authors present novel algorithms for selecting an elements of specified rank among N=n² elements on an n×n mesh-connected processor array, in a variety of settings. They give: (1) an optimal randomized algorithm for selecting the element of rank k out of N, 1⩽k ⩽N, at any processor that is at least 0.5n- o(n) steps away from the middle processor; (2) an optimal deterministic algorithm for selecting the element of rank k out of N, 1⩽k⩽N, at any processor, when the elements are drawn from the set {1,. . .,N ^1-∈}, where 0<∈⩽1; and an optimal deterministic algorithm for selecting the element of rank k out of N, at any processor, when 1⩽k⩽N ^1-∈, where 0<∈⩽1