Parallel Pseudo-Merge Sorting on a Mesh-Connected Processor Array

Koji SAGA  Kazuhiro SADO  Yoshihide IGARASHI  

IEICE TRANSACTIONS (1976-1990)   Vol.E69   No.10   pp.1104-1113
Publication Date: 1986/10/25
Online ISSN: 
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Algorithm, Computational Complexity

Full Text: PDF>>
Buy this Article

A fast parallel sorting algorithm on a mesh-connected processor array is presented. The algorithm is based on a pseudo-merge algorithm that roughly merges four roughly sorted subfiles. Its computing time for sorting N items is 6+3log213 steps. We also discuss lower bounds on computing times for four classes of parallel sorts, bubble merge sorts, bubble-exchange merge sorts, bubble pseudo-merge sorts and bubble-exchange pseudo-merge sorts. It is shown that 4.54log2 steps, 3.52log21 steps, 34log2+3 steps and 2.5log21 steps, are lower bounds for these classes, respectively.