# MPI-I-94-137

## Improved parallel integer sorting without concurrent writing

### Albers, Susanne and Hagerup, Torben

**MPI-I-94-137**. July** **1994, ? pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

We show that $n$ integers in the range

$1 \twodots n$ can be stably sorted on an

\linebreak EREW PRAM

using \nolinebreak $O(t)$ time \linebreak and

$O(n(\sqrt{\log n\log\log n}+{{(\log n)^2}/t}))$

operations, for arbitrary given \linebreak

$t\ge\log n\log\log n$, and on a CREW PRAM using

%$O(\log n\log\log n)$ time and $O(n\sqrt{\log n})$

$O(t)$ time and

$O(n(\sqrt{\log n}+{{\log n}/{2^{{t/{\log n}}}}}))$

operations, for arbitrary given $t\ge\log n$.

In addition, we are able to sort $n$ arbitrary

integers on a randomized CREW PRAM

% using

%$O(\log n\log\log n)$ time and $O(n\sqrt{\log n})$ operations

within the same resource bounds with high probability.

In each case our algorithm is

a factor of almost $\Theta(\sqrt{\log n})$

closer to optimality

than all previous algorithms for the stated problem

in the stated model, and our third result matches the operation

count of the best known sequential algorithm.

We also show that $n$ integers in the range $1 \twodots m$

can be sorted in $O((\log n)^2)$

time with $O(n)$ operations on an EREW PRAM using a nonstandard word

length of $O(\log n \log\log n \log m)$ bits,

thereby greatly improving the upper

bound on the word length necessary to sort integers

with a linear time-processor product,

even sequentially.

Our algorithms were inspired by, and in one case directly

use, the fusion trees of

Fredman and Willard.

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-94-137.pdf | 17166 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/1994-137

**BibTeX**
`@TECHREPORT{``AlbersHagerup94``,`

` AUTHOR = {Albers, Susanne and Hagerup, Torben},`

` TITLE = {Improved parallel integer sorting without concurrent writing},`

` TYPE = {Research Report},`

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

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

` NUMBER = {MPI-I-94-137},`

` MONTH = {July},`

` YEAR = {1994},`

` ISSN = {0946-011X},`

`}`