Published online by Cambridge University Press: 01 July 2016
Radix Sort is a sorting algorithm based on analyzing digital data. We study the number of swaps made by Radix Select (a one-sided version of Radix Sort) to find an element with a randomly selected rank. This kind of grand average provides a smoothing over all individual distributions for specific fixed-order statistics. We give an exact analysis for the grand mean and an asymptotic analysis for the grand variance, obtained by poissonization, the Mellin transform, and depoissonization. The digital data model considered is the Bernoulli(p). The distributions involved in the swaps experience a phase change between the biased cases (p ≠ ½) and the unbiased case (p = ½). In the biased cases, the grand distribution for the number of swaps (when suitably scaled) converges to that of a perpetuity built from a two-point distribution. The tool for this proof is contraction in the Wasserstein metric space, and identifying the limit as the fixed-point solution of a distributional equation. In the unbiased case the same scaling for the number of swaps gives a limiting constant in probability.
Part of this work was carried out while the author was at Max-Planck-Institut für Informatik. The author is currently on leave from Alexandria University of Egypt.