Abstract
In this paper, we study the merging of two sorted arrays
and
on EREW PRAM with two restrictions: (1) The elements of two arrays are taken from the integer range [1,
n
], where
n
=
Max
(
n
1
,
n
2
). (2) The elements are taken from either uniform distribution or non-uniform distribution such that
, for 1≤
i
≤
p
(number of processors). We give a new optimal deterministic algorithm runs in
time using
p
processors on EREW PRAM. For
; the running time of the algorithm is
O
(log
(
g
)
n
) which is faster than the previous results, where log
(
g
)
n
=log log
(
g
−1)
n
for
g
>1 and log
(1)
n
=log
n
. We also extend the domain of input data to [1,
n
k
], where
k
is a constant.