Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


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:
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.
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.pdfMPI-I-92-141.pdf18992 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:
Hide details for BibTeXBibTeX
  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},