Sorting algorithms for broadcast communications: mathematical analysis

AbstractWe study three algorithms for sorting under the broadcast communication model. Two algorithms are based on the maximum finding and the loser selection strategy, the third one is the naı̈ve strategy based on loser selection only. While a precise description of the algorithms can be found in the paper [15], we concentrate here on the mathematical aspects of the analysis. From these elementary considerations it follows that the average time complexities of the non-naı̈ve algorithms are Θ(n). We give precise expressions for the constants involved by writing them as contour integrals involving zeta functions. The numerical evaluation via residues leads to slowly converging series, and the acceleration of them is a non-trivial task that is done in a slightly more general fashion in order to fit all the applications