scientific article; zbMATH DE number 4049075

From MaRDI portal
Publication:3785964





[For the entire collection see Zbl 0636.00011.] By investigating the property of the parallel bubbling, we evaluate the exact number of operations necessary to move each item to its final position by the parallel bubble sort. This evaluation is useful for designing efficient parallel sorts on a mesh-connected processor array and for analyzing their time efficiency. Two parallel sorts on the mesh- connected model are shown. We also discuss lower bounds on computing time for the class of iterative merge sorts and the class of iterative pseudo-merge sorts. It is shown that \(4.5 \sqrt{N}-3 \log_ 2 \sqrt{N}-2\) steps and \(3.5 \sqrt{N}- \log_ 2 \sqrt{N}-3\) steps are lower bounds for these classes, where N is the number of items to be sorted.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3785964)