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.