For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Time Lower Bounds for Merge Sorts and Pseudo-Merge Sorts on Mesh-Connected Processor Arrays
Yoshihide IGARASHI Kazuhiro SADO Koji SAGA
IEICE TRANSACTIONS (1976-1990)
Publication Date: 1987/09/25
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity
Full Text: PDF>>
We discuss time lower bounds for iterative merge sorts and iterative psueudo-merge sorts on an nn meshconnected processor array. They are 4.5n-3log2n-2 steps and 3.5n-log2n-3 steps for sorting n2 items. We also discuss time lower bounds for these sorting algorithms on higher dimensional models. For the case of the three-dimensional mesh-connected model, 7.25n-4log2n-8 steps and 5.25n-log2n-6 steps are lower bounds for sorting n3 items by iterative merge sorts and iterative pseudo-merge sorts, respectively.