Fast Parallel Sorting on a Mesh-Connected Processor Array

Kazuhiro SADO; Yoshihide IGARASHI

Fast Parallel Sorting on a Mesh-Connected Processor Array

Kazuhiro SADO, Yoshihide IGARASHI

Full Text Views

0

Share
Cite this

Summary :

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 n² 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.

Publication: IEICE TRANSACTIONS on transactions Vol.E71-E No.4 pp.422-430

Publication Date: 1988/04/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Algorithm and Computational Complexity

Authors

Kazuhiro SADO
Yoshihide IGARASHI

Keyword

Cite this

Copy

Kazuhiro SADO, Yoshihide IGARASHI, "Fast Parallel Sorting on a Mesh-Connected Processor Array" in IEICE TRANSACTIONS on transactions, vol. E71-E, no. 4, pp. 422-430, April 1988, doi: .
Abstract: 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 n² 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.
URL: https://globals.ieice.org/en_transactions/transactions/10.1587/e71-e_4_422/_p

Copy

@ARTICLE{e71-e_4_422,
author={Kazuhiro SADO, Yoshihide IGARASHI, },
journal={IEICE TRANSACTIONS on transactions},
title={Fast Parallel Sorting on a Mesh-Connected Processor Array},
year={1988},
volume={E71-E},
number={4},
pages={422-430},
abstract={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 n² 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.},
keywords={},
doi={},
ISSN={},
month={April},}

Copy

TY - JOUR
TI - Fast Parallel Sorting on a Mesh-Connected Processor Array
T2 - IEICE TRANSACTIONS on transactions
SP - 422
EP - 430
AU - Kazuhiro SADO
AU - Yoshihide IGARASHI
PY - 1988
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E71-E
IS - 4
JA - IEICE TRANSACTIONS on transactions
Y1 - April 1988
AB - 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 n² 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.
ER -