Rates of convergence for Quicksort

DOI10.1016/S0196-6774(02)00206-7zbMath1010.68049OpenAlexW2137320372MaRDI QIDQ4799522

Ralph Neininger, Ludger Rüschendorf

Publication date: 23 March 2003

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0196-6774(02)00206-7

zbMATH Keywords

rate of convergenceanalysis of algorithmscontraction methodquicksortlocal approximationZolotarev metric

Mathematics Subject Classification ID

Searching and sorting (68P10) General topics in the theory of algorithms (68W01)

Related Items (10)

Distribution of distances in random binary search trees. ⋮ On the contraction method with degenerate limit equation. ⋮ Central limit theorem in uniform metrics for generalized Kac equations ⋮ Distributional convergence for the number of symbol comparisons used by QuickSort ⋮ Analysis of the expected number of bit comparisons required by quickselect ⋮ A general limit theorem for recursive algorithms and combinatorial structures ⋮ Random binary trees: from the average case analysis to the asymptotics of distributions ⋮ On martingale tail sums for the path length in random trees ⋮ Refined quicksort asymptotics ⋮ A note on the quicksort asymptotics

This page was built for publication: Rates of convergence for Quicksort