Data Movement in Odd-Even Merging
Robert Sedgewick · SIAM Journal on Computing · 1978
A complete analysis is given of the number of exchanges used by the well-known Batcher’s odd-even merging (and sorting) networks. Batcher’s method involves a fixed sequence of “compare-exchange” operations, so the number of comparisons required is easy to compute, but the problem of determining how many comparisons result in exchanges has not been successfully attacked before. New results are derived in this paper giving accurate formulas for the worst-case and average values of this quantity. The worst-case analysis leads to the unexpected result that, asymptotically, the ratio of exchanges to comparisons approaches 1, although convergence to this asymptotic maximum is very slow. The average-case analysis shows that, asymptotically, only $\frac{1}{4}$ of the comparators are involved in exchanges. The method used to derive this result can in principle be used to get any asymptotic accuracy. The derivation involves principles of the theory of complex functions; in particular, properties of the $\Gamma $-function and the generalized Riemann $\zeta $-function are integral to the solution. Intermediate results in the analysis may be applicable to the average-case analysis of other merging methods, and the final portion of the derivation illustrates the utility of the “gamma function” method of asymptotic analysis.