Abstract
We present an
O(log(min(
m,
n,
j))-time sequential algorithm to select the
jth-smallest element of an array resulting from the merging of two sorted arrays
A and
B of sizes
m and
n. This algorithm is then used to design two parallel algorithms to partition
A and
B into
p subarrays of size
O(
(m + n)
p
)
in
O(
N
p
+ log N)
and
O(
N
p
+
log p
log N)
times on
crew pram and
erew pram models with
p processors, where
N =
m +
n. A third parallel algorithm has been presented that partitions
A and
B in
O(
N
p
+
log p
log N)
time into
p pairs of subarrays of size
O(
N
p
)
on
erew pram with
p processors without using any selection algorithm. Finally, these partitioning algorithms are used to obtain optimal parallel merging and sorting algorithms on
crew prams and
erew prams.
