For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Fast Parallel Sorting on a Mesh-Connected Processor Array
Kazuhiro SADO Yoshihide IGARASHI
IEICE TRANSACTIONS (1976-1990)
Publication Date: 1988/04/25
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity
Full Text: PDF>>
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.