Randomized sorting and selection on mesh-connected processor arrays (preliminary version)
Christos Kaklamanis, Danny Kriz̧anc, Lata Narayanan, Thanasis Tsantilas · 1991
we show that sorting an input of size N = n2 can be performed by an n x n mesh-connected processor array in 2.5n + o(n) parallel communication steps and using constant size queues, with high probability.The best previously known algorithm for this problem required 37L + o(n) steps.We also show that selecting the element of rank k out of N = n2 inputs on an n x n mesh can be performed in 1.25n + o(n) steps and using constant size queues, with high probability.The best previously known algorithm for this problem involved sorting, and required 3n + o(n) steps.Both of our algorithms can be generalized to higher dimensions, achieving bounds better than the known results.