Abstract
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 language | English (US) |
|---|---|
| Pages (from-to) | 141-152 |
| Number of pages | 12 |
| Journal | Computers and Artificial Intelligence |
| Volume | 16 |
| Issue number | 2 |
| State | Published - 1997 |
| Externally published | Yes |
Keywords
- Average performance
- Mesh-connected computer
- Optimal algorithm
- Parallel algorithm
- Selection
- Sorting
ASJC Scopus subject areas
- General Computer Science