Mesh Sorting and Selection Optimal to the Average

Abstract

We consider 1-1 sorting and selection problems on an n x n mesh-connected processor arrays. Algorithms are developed which are fast with respect to the average-time performance. We show that selection can be accomplished in the average time 2-n + o(n), and sorting in the average time 2 . n+o(n). Matching lower bounds are also proved.