On Batcher's Merge Sorts as Parallel Sorting Algorithms

摘要

We examine the average running times of Batcher's bitonic merge and Batcher's odd-even merge when they are used as parallel merging algorithms. It has been shown previously that the running time of odd-even merge can be upper bounded bya function of the maximal rnak difference for elements in the two input sequence.s Here we give an almost matching lower bound for odd-even merge as well as a similar upper bound for bitonic merge. From this follows that the average running time of odd-even merge is sita(n/p)(1+log(1+p sup 2)))(O((n/p)(1+log(1+p sup 2))), resp.) where n is the size ofthe input and p is the number of processors. Using these results we then show that the average runnign times ofodd-even merge sort and bitonic merge sort are O((n/p)(log n+(log(1+p sup 2)) sup 2), that is, the two algorithms are optimal on the aerage if n greater than or equal to P sup 2/2 square root of (log p).