How to cite item

A Characterization of the Set of Fixed Points of the Quicksort Transformation

   
@article{ECP1021,
	author = {James Fill and Svante Janson},
	title = {A Characterization of the Set of Fixed Points of the Quicksort Transformation},
	journal = {Electron. Commun. Probab.},
	fjournal = {Electronic Communications in Probability},
	volume = {5},
	year = {2000},
	keywords = {Quicksort, fixed point, characteristic function, smoothing transformation,domain of attraction, coupling, integral equation},
	abstract = {The limiting distribution $\mu$ of the normalized number of key comparisons required by the Quicksort sorting algorithm is known to be the unique fixed point of a certain distributional transformation $T$ - unique, that is, subject to the constraints of zero mean and finite variance. We show that a distribution is a fixed point of $T$ if and only if it is the convolution of $\mu$ with a Cauchy distribution of arbitrary center and scale. In particular, therefore, $\mu$ is the unique fixed point of $T$ having zero mean.},
	pages = {no. 9, 77-84},
	issn = {1083-589X},
	doi = {10.1214/ECP.v5-1021},    
        url = {http://ecp.ejpecp.org/article/view/1021}}