MPI-INF/SWS Research Reports 1991-2021

1. Author,Editor - 3. with BibTeX cite keys


Fast parallel space allocation, estimation an integer sorting

Hagerup, Torben

June 1991, 28 pages.

Status: available - back from printing

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.

  • MPI-I-91-106.pdf
  • Attachement: MPI-I-91-106.pdf (15501 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  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},