Publication IEICE TRANSACTIONS (1976-1990)Vol.E69No.10pp.1104-1113 Publication Date: 1986/10/25 Online ISSN: DOI: Print ISSN: 0000-0000 Type of Manuscript: PAPER Category: Algorithm, Computational Complexity Keyword:
Full Text: PDF>>
Summary: 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.