Batcher's odd–even exchange revisited: A generating functions approach

In the celebrated odd–even exchange algorithm by Batcher, the quantity average number of exchanges is one of the fundamental quantities of interest. It was a mystery a few years ago and is still tricky today. We provide an approach that is purely based on generating functions to provide an explicit expression. The asymptotic analysis was done several years ago but never published in a journal and is thus provided here as well in condensed form. It is a combination of singularity analysis of generating functions and Mellin transform techniques.