Merging with Parallel Processors

Consider two linearly ordered sets A, B, |A|=m,
|B|=n, m<=n, and p, p<=m, parallel processors 
working synchronously.  The paper presents an algorithm
for merging A and B with the p parallel processors, 
which requires at most 2[log2 (2m+1)]+[3m/p] + [m/p][log2
(n/m)] steps.  If n = (2^B)m (B an integer), 
the algorithm requires at most 2[log2 (m+1)] + [m/p](2+B)
steps.  In the case where m and n are of the 
same order of magnitude, i.e. n=km with k being a constant,
the algorithm requires 2[log2 (m+1)] + [m/p](3+k) 
steps.  These performances compare very favorably with
the previous best parallel merging algorithm, 
Batcher's algorithm, which requires n/p + ((m+n)/2p)log2 m
steps in the general case and km/p + ((k+1)/2)(m/p)log2 
m in the special case where n=km.

CACM October, 1975

Gavril, F.

parallel processing, parallel merging, parallel binary insertion

5.31

CA751005 JB January 6, 1978  10:50 AM

2714	4	2714
3075	4	2714
2664	5	2714
2714	5	2714
2714	5	2714
2714	5	2714
3075	5	2714
2289	6	2714
2557	6	2714
2664	6	2714
2714	6	2714