On the average running time of odd-even merge sort

This paper is concerned with the average running time of Batcher's odd-even merge sort when implemented on a collection of processors. We consider the case where the size n of the input is an arbitrary multiple of the number p of processors used. We show that Batcher's odd-even merge (for two sorted lists of length m each) can be implemented to run in time O((m/p)(1+log(1+p2/m))) on the average, and that odd-even merge sort can be implemented to run in time O((n/p)(log(n/p)+logp(1+log(1+p2/n)))) on the average. In the case of merging (sorting) the average is taken over all possible outcomes of the merging (all possible permutations of n elements). That means that odd-even merge and odd-even merge sort have an optimal average running time if n≥p2.