# MPI-I-92-141

## Waste makes haste: tight bounds for loose parallel sorting

### Hagerup, Torben and Raman, Rajeev

**MPI-I-92-141**. September** **1992, 185 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

Conventional

parallel sorting requires the $n$ input

keys to be output in an array of size $n$, and is known to

take $\Omega({{\log n}/{\log\log n}})$ time using

any polynomial number of processors.

The lower bound does not apply to the more ``wasteful''

convention of {\em padded sorting}, which

requires the keys to be output in sorted order in

an array of size $(1 + o(1)) n$.

We give very fast randomized CRCW PRAM algorithms for

several padded-sorting problems.

Applying only pairwise comparisons to the input

and using $kn$ processors, where $2\le k\le n$,

we can padded-sort $n$ keys in

$O({{\log n}/{\log k}})$ time with

high probability (whp), which

is the best possible (expected)

run time for any comparison-based algorithm.

We also show how to padded-sort

$n$ independent random numbers

in $O(\log^*\! n)$ time whp with $O(n)$ work,

which matches a recent lower bound,

and how to padded-sort

$n$ integers in the range $ 1..n $

in constant time whp using $n$ processors.

If the integer sorting is required to be stable,

we can still solve the problem in

$O({{\log\log n}/{\log k}})$ time whp using

$kn$ processors, for any $k$ with $2\le k\le\log n$.

The integer sorting results require the

nonstandard OR PRAM; alternative implementations

on standard PRAM variants run in $O(\log\log n)$ time whp.

As an application of our padded-sorting algorithms,

we can solve approximate prefix summation problems

of size~$n$ with $O(n)$ work

in constant time whp on the OR PRAM,

and in $O(\log\log n)$ time whp on

standard PRAM variants.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

MPI-I-92-141.pdf | 18992 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1992-141

**BibTeX**
`@TECHREPORT{``HagerupRaman92``,`

` AUTHOR = {Hagerup, Torben and Raman, Rajeev},`

` TITLE = {Waste makes haste: tight bounds for loose parallel sorting},`

` TYPE = {Research Report},`

` INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},`

` ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-92-141},`

` MONTH = {September},`

` YEAR = {1992},`

` ISSN = {0946-011X},`

`}`