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

      0 references
      0 references
      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
      [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

      Identifiers