Fast Integer Merging on the EREW PRAM
Torben Hagerup, Miroslaw Kutylowski
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(loglog n) time. More generally, we
describe an algorithm to merge two sorted sequences of n integers drawn
from the set {0,...,m-1} in O(loglog 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,...,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.