Fast Parallel Sorts on a Practical Sized Mesh-Connected Processor Array

Yoshihide IGARASHI  Kazuhiro SADO  Koji SAGA  

IEICE TRANSACTIONS (1976-1990)   Vol.E70   No.1   pp.56-64
Publication Date: 1987/01/25
Online ISSN: 
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Algorithm, Computational Complexity

Full Text: PDF>>
Buy this Article

We show some properties of the parallel bubble sort and propose three parallel sorting algorithms on the mesh-connected processor array. These algorithms are some combinations of the parallel bubble sorts in different directions. The hardware structure and control for these algorithms are simple. These abgorithms seem to be asymptotically slower than O()-time parallel sorting algorithms. However, our computer experiments show that two of our abgorithms are faster on the average than any known algorithm on the mesh-connected model for N16384.