No label defined (Q3785964)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4049075
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4049075 |
Statements
1987
0 references
parallel sorting
0 references
VLSI
0 references
parallel bubbling
0 references
bubble sort
0 references
mesh-connected processor array
0 references
iterative merge sorts
0 references
0.8569375276565552
0 references
0.8362836837768555
0 references
0.8165555000305176
0 references
[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.
0 references