Average-case results on heapsort

1987/03/01 by Svante Carlsson · 5 citations
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #semigroups and automata theory

paper · doi:10.1007/bf01937350

crossref issued 1987/03/01 · crossref published 1987/03/01 · crossref published-print 1987/03/01 · openalex publication_date 1987/03/01 · crossref created 2005/07/25 · crossref deposited 2021/07/14 · crossref indexed 2023/08/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Citations

• Algorithm 245: Treesort
• A variant of heapsort with almost optimal number of comparisons
• Algorithm 230: Matrix Permutation

Cited by

• The worst case complexity of McDiarmid and Reed's variant of BOTTOM-UP HEAPSORT is less than n log n + 1.1n
• A tight lower bound for the worst case of Bottom-Up-Heapsort
• BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT beating, on an average, QUICKSORT (if n is not very small)
• A meticulous analysis of mergesort programs
• Heapsort [wikipedia]