Quicksort asymptotics

DOI10.1016/S0196-6774(02)00216-XzbMath1011.68028arXivmath/0105248MaRDI QIDQ4799520

James Allen Fill, Svante Janson

Publication date: 23 March 2003

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

Full work available at URL: https://arxiv.org/abs/math/0105248

zbMATH Keywords

rate of convergenceasymptoticsdensitymoment generating functioncouplinglimit distributionnumerical analysisQuicksortsorting algorithmKolmogorov-Smirnov distance\(d_2\)-metric

Mathematics Subject Classification ID

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

Related Items (17)

Approximating perpetuities ⋮ Second phase changes in random \(m\)-ary search trees and generalized quicksort: Convergence rates ⋮ Density functions for \texttt{QuickQuant} and \texttt{QuickVal} ⋮ Distributional convergence for the number of symbol comparisons used by QuickSort ⋮ Analysis of the expected number of bit comparisons required by quickselect ⋮ A weakly 1-stable distribution for the number of random records and cuttings in split trees ⋮ Non-asymptotic distributional bounds for the Dickman approximation of the running time of the Quickselect algorithm ⋮ The total path length of split trees ⋮ On martingale tail sums for the path length in random trees ⋮ Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise ⋮ Random Records and Cuttings in Binary Search Trees ⋮ An efficient algorithm for overcomplete sparsifying transform learning with signal denoising ⋮ Refined quicksort asymptotics ⋮ Upper tail analysis of bucket sort and random tries ⋮ Upper tail analysis of bucket sort and random tries ⋮ QuickSort: improved right-tail asymptotics for the limiting distribution, and large deviations ⋮ A note on the quicksort asymptotics

This page was built for publication: Quicksort asymptotics