Selection on the reconfigurable mesh
Eric Hao, PHILIP D. MACKENZIE, Quentin F. Stout · 1992
A Theta (log n) time algorithm to select the kth smallest element in a set of n elements on a reconfigurable mesh with n processors is obtained. This improves on the previous fastest algorithm's running time by a factor of log n. It is also shown that variants of this problem can be solved even faster. Finally, a proof of Omega (log log n) lower bound time for the rmesh selection problem is given.>