scientific article; zbMATH DE number 4049075
[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.
- Time lower bounds for parallel sorting on a mesh-connected processor array
- Lower bounds for sorting on mesh-connected architectures
- scientific article; zbMATH DE number 3958741
- Time lower bounds for sorting on multi-dimensional mesh-connected processor arrays
- scientific article; zbMATH DE number 4035170
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)