Fast Parallel Sorting on a Mesh-Connected Processor Array

Kazuhiro SADO  Yoshihide IGARASHI  

IEICE TRANSACTIONS (1976-1990)   Vol.E71   No.4   pp.422-430
Publication Date: 1988/04/25
Online ISSN: 
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity

Full Text: PDF>>
Buy this Article

Two fast parallel sorting algorithms on a mesh-connected model are described. These algorithms are some combinations of row and column sorts, and use just the compare-exchange as their basic operation. The computing time of the first algorithm for sorting n2 items is 6.5n+2 log n-5 steps and the computing time of the second one is not more than 5.5n+0.5 log n+0.5 +1.5 log n-3 steps. The control structures of these algorithms are particularly simple. The correctness of the algorithms are proved in a lucid way by using a function POTENTIAL. The function evaluates the exact number of steps to sort items by parallel bubble sort.