Running time of the treapsort algorithm

DOI10.1016/J.TCS.2013.03.012MaRDI QIDQ387004zbMATH OpenOpenAlexFDO

Authors D. Early, M. Schellekens

Publication date 11 December 2013

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2013.03.012

zbMATH Keywords

\(\mathcal{MOQA}\)average-case analysis of algorithmssmoothed complexitysorting algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10)

Recommendations

• Smoothsort revisited
• Randomized adaptive sorting
• Linear-time construction of treaps and Cartesian trees
• Sorting algorithms in \textsc{MOQA}
• QuickHeapsort, an efficient mix of classical sorting algorithms

Cites work

• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 1540682 (Why is no real title available?)
• scientific article; zbMATH DE number 1552325 (Why is no real title available?)
• scientific article; zbMATH DE number 742989 (Why is no real title available?)
• A limiting distribution for quicksort
• Mathematical Foundations of Computer Science 2003
• Smoothed analysis of algorithms
• Smoothed analysis of algorithms and heuristics: progress and open questions
• Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time
• Some properties of a limiting distribution in Quicksort
• \(\mathcal{MOQA}\); unlocking the potential of compositional static average-case analysis

Cited in

(1)

• Entropy conservation for comparison-based algorithms

This page was built for publication: Running time of the treapsort algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q387004)