Sorting algorithms for broadcast communications: mathematical analysis

摘要

We 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 naive 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-naive 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.