Running time of the treapsort algorithm

DOI10.1016/J.TCS.2013.03.012zbMATH Open1293.68316OpenAlexW1977694409MaRDI QIDQ387004FDOQ387004

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Smoothed analysis of algorithms
• \(\mathcal{MOQA}\); unlocking the potential of compositional static average-case analysis
• Title not available (Why is that?)
• Some properties of a limiting distribution in Quicksort
• Smoothed analysis of algorithms and heuristics: progress and open questions
• A limiting distribution for quicksort
• Title not available (Why is that?)
• Title not available (Why is that?)
• Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time
• Mathematical Foundations of Computer Science 2003

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)