# MPI-I-92-115

## 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.

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-92-115.pdf | 9383 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/1992-115

**BibTeX**
`@TECHREPORT{``HagerupKutylowski92``,`

` 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},`

`}`