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


Fast integer merging on the EREW PRAM

Hagerup, Torben and Kutylowski, Miroslaw

MPI-I-92-115. March 1992, 12 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
We investigate the complexity of merging sequences of small integers
on the EREW PRAM.
Our most surprising result is that two sorted sequences
of $n$ bits each can be merged in $O(\log\log n)$ time.
More generally, we describe an algorithm to merge two
sorted sequences of $n$ integers drawn from the set
$\{0,\ldots,m-1\}$ in $O(\log\log n+\log m)$ time
using an optimal number of processors.
No sublogarithmic merging algorithm for this model
of computation was previously known.
The algorithm not only produces the merged sequence, but also
computes the rank of each input element in the merged sequence.
On the other hand, we show a lower bound of
$\Omega(\log\min\{n,m\})$ on the time needed
to merge two sorted sequences of length $n$ each
with elements in the set $\{0,\ldots,m-1\}$,
implying that our merging algorithm is as fast
as possible for $m=(\log n)^{\Omega(1)}$.
If we impose an additional stability condition
requiring the ranks of each input sequence to
form an increasing sequence, then the time
complexity of the problem becomes $\Theta(\log n)$,
even for $m=2$.
Stable merging is thus harder than nonstable merging.
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-115.pdfMPI-I-92-115.pdf9383 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 Kutylowski, Miroslaw},
  TITLE = {Fast integer merging on the EREW PRAM},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-92-115},
  MONTH = {March},
  YEAR = {1992},
  ISSN = {0946-011X},