Mesh Sorting and Selection Optimal to the Average

Authors

  • B. S. Chlebus

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.

Downloads

Download data is not yet available.

Published

2012-03-05

How to Cite

Chlebus, B. S. (2012). Mesh Sorting and Selection Optimal to the Average. COMPUTING AND INFORMATICS, 16(2), 141–152. Retrieved from https://www.cai.sk/ojs/index.php/cai/article/view/665