Publication IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer SciencesVol.E76-ANo.11pp.2008-2015 Publication Date: 1993/11/25 Online ISSN: DOI: Print ISSN: 0916-8508 Type of Manuscript: PAPER Category: Computer Aided Design (CAD) Keyword: sorting, parallel algorithm, processor array, bus,
Full Text: PDF(648.6KB)>>
Summary: This paper presents a parallel sorting algorithm which sorts n elements on O(n/w+n log n/p) time using p(n) processors arranged in a 1-dimensional grid with w(n1-ε) buses for every fixed ε>0. Furthermore, it is shown that np elements can be sorted in O(n/w+n log n/p) time on pp (pn) processors arranged in a 2-dimensional grid with w(n1-ε) buses in each column and in each row. These algorithms are optimal because their time complexities are equal to the lower bounds.