English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

Fast parallel space allocation, estimation and integer sorting (revised)

MPS-Authors
/persons/resource/persons44076

Bast,  Holger
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44564

Hagerup,  Torben
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

MPI-I-93-123.pdf
(Any fulltext), 48MB

Supplementary Material (public)
There is no public supplementary material available
Citation

Bast, H., & Hagerup, T.(1993). Fast parallel space allocation, estimation and integer sorting (revised) (MPI-I-93-123). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-B74E-F
Abstract
The following problems are shown to be solvable in $O(\log^{\ast }\! n)$ time with optimal speedup with high probability on a randomized CRCW PRAM using $O(n)$ space: \begin{itemize} \item Space allocation: Given $n$ nonnegative integers $x_1,\ldots,x_n$, allocate $n$ nonoverlapping blocks of consecutive memory cells of sizes $x_1,\ldots,x_n$ from a base segment of $O(\sum_{j=1}^n x_j)$ consecutive memory cells; \item Estimation: Given $n$ integers %$x_1,\ldots,x_n$ in the range $ 1.. n $, compute ``good'' estimates of the number of occurrences of each value in the range $1.. n$; \item Semisorting: Given $n$ integers $x_1,\ldots,x_n$ in the range $1.. n$, store the integers $1,\ldots,n$ in an array of $O(n)$ cells such that for all $i\in\{1,\ldots,n\}$, all elements of $\{j:1\le j\le n$ and $x_j=i\}$ occur together, separated only by empty cells; \item Integer chain-sorting: Given $n$ integers $x_1,\ldots,x_n$ in the range $1.. 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$. \end{itemize} \noindent Moreover, given slightly superlinear processor and space bounds, these problems or variations of them can be solved in constant time with high probability. As a corollary of the integer chain-sorting result, it follows that $n$ integers in the range $1.. n$ can be sorted in $O({{\log n}/{\log\log n}})$ time with optimal speedup with high probability.