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)   Vol.E70   No.9   pp.865-871
Publication Date: 1987/09/25
Online ISSN: 
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity

Full Text: PDF>>
Buy this Article

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.