Optimal Sorting Algorithms on Bus-Connected Processor Arrays


IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E76-A   No.11   pp.2008-2015
Publication Date: 1993/11/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Computer Aided Design (CAD)
sorting,  parallel algorithm,  processor array,  bus,  

Full Text: PDF(648.6KB)>>
Buy this Article

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.