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