Abstract
Given two ordered multisets $A$ and $B$, of sizes $m$ and $n$ respectively, where $m \leq n$, and a sequence of $r$ integers $1 \leq K_1 < K_2 < \ldots < K_r \leq (m+n)$, the {\em multiselection} problem is to find all the $K_i$th, $1 \leq i \leq r$, smallest elements in $A+B$, the combined elements of the two arrays, without explicitly merging the arrays. We present an $O(\log m + \log r)$ time algorithm using $r$ processors on the EREW PRAM. A careful analysis of our parallel multiselection algorithm shows that the total number of comparisons performed is $O(r \log (m/r))$, when $r \leq m$, and $O(m \log (r/m))$, when $m \leq r$, which matches the information-theoretic lower bound on the problem of multiselection.
A natural way to merge two sorted arrays in parallel is to partition the arrays into equal size subarrays such that independent merging of the subarrays solves the original problem. Thus, the problem of merging in parallel can be solved if we can efficiently select the correct elements to partition the arrays. Our multiselection algorithm was used to select the correct elements, leading to a simple and optimal algorithm for merging on the EREW PRAM requiring $O(\log(m+n))$ time and $O(m+n)$ work. The merging algorithm does not move or copy any data during the partitioning phase and the number of comparisons is within lower order terms of the minimum possible, even by a sequential algorithm. Hagerup and R\"ub~\cite{hr:omsep} have given a parallel merging algorithm on the EREW PRAM that has the minimum number of comparisons for any parallel merging algorithm for the EREW PRAM. Our merging algorithm has the same number of comparisons when $m = \Theta(n)$. When the size of the two lists differs significantly, however, our merging algorithm performs asymptotically fewer comparisons than Hagerup and \Rub's algorithm.
Appeared in: Information Prcessing Letters, volume 50 (1994), pp. 81--87
View the PostScript document.