# MPI-I-91-106

## Fast parallel space allocation, estimation an integer sorting

### Hagerup, Torben

**MPI-I-91-106**. June** **1991, 28 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

We show that each of the following problems can be solved

fast and with optimal speedup with high probability on a

randomized CRCW PRAM using

$O(n)$ space:

Space allocation: Given $n$ nonnegative integers

$x_1,\ldots,x_n$, allocate $n$ blocks of consecutive

memory cells of sizes $x_1,\ldots,x_n$ from a base

segment of $O(\sum_{i=1}^n x_i)$ consecutive

memory cells;

Estimation: Given $n$ integers %$x_1,\ldots,x_n$

in the range $1\Ttwodots n$, compute ``good'' estimates

of the number of occurrences of each value

in the range $1\Ttwodots n$;

Integer chain-sorting: Given $n$ integers $x_1,\ldots,x_n$

in the range $1\Ttwodots n$, construct a linked list

containing the integers $1,\ldots,n$ such that for all

$i,j\in\{1,\ldots,n\}$, if $i$ precedes $j$ in the

list, then $x_i\le x_j$.

\noindent

The running times achieved are $O(\Tlogstar n)$ for

problem (1) and $O((\Tlogstar n)^2)$ for

problems (2) and~(3).

Moreover, given slightly superlinear processor

and space bounds, these problems or variations

of them can be solved in

constant expected time.

Acknowledgement:** **

References to related material:

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

| 15501 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/1991-106

**BibTeX**
`@TECHREPORT{``Hagerup91a``,`

` AUTHOR = {Hagerup, Torben},`

` TITLE = {Fast parallel space allocation, estimation an integer sorting},`

` TYPE = {Research Report},`

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

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

` NUMBER = {MPI-I-91-106},`

` MONTH = {June},`

` YEAR = {1991},`

` ISSN = {0946-011X},`

`}`