MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


Fast integer merging on the EREW PRAM

Hagerup, Torben and Kutylowski, Miroslaw

March 1992, 12 pages.

Status: available - back from printing

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.

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