hide
Free keywords:
-
Abstract:
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.
