Mesh sorting and selection optimal on the average

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


We consider 1-1 sorting and selection problems on an n × 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 n + o(n), and sorting in the average time 2 · n + o(n). Matching lower bounds are also proved.

Original languageEnglish (US)
Pages (from-to)141-152
Number of pages12
JournalComputers and Artificial Intelligence
Issue number2
StatePublished - Dec 1 1997
Externally publishedYes


  • Average performance
  • Mesh-connected computer
  • Optimal algorithm
  • Parallel algorithm
  • Selection
  • Sorting

ASJC Scopus subject areas

  • Computer Science(all)


Dive into the research topics of 'Mesh sorting and selection optimal on the average'. Together they form a unique fingerprint.

Cite this