Merging with parallel processors

Abstract

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⌈log ₂ (2 m + 1)⌉ + ⌊3 m / p ⌋ + [ m / p ][log ₂ ( n / m )] steps. If n = 2 ^β m ( β an integer), the algorithm requires at most 2[log ₂ ( m + 1)] + [ m / p ](2 + β ) 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[log ₂ ( 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 )/2 p )log ₂ m steps in the general case and km / p + (( k + 1)/2)( m / p )log ₂ m in the special case where n = km .