A variant of heapsort with almost optimal number of comparisons

1987/03/01 by Svante Carlsson · 5 citations
Computer Science · #Algorithms and Data Compression #Handwritten Text Recognition Techniques #Machine Learning and Algorithms

paper · doi:10.1016/0020-0190(87)90142-6

crossref issued 1987/03/01 · crossref published 1987/03/01 · crossref published-print 1987/03/01 · openalex publication_date 1987/03/01 · crossref created 2003/03/14 · crossref deposited 2021/06/05 · crossref indexed 2025/03/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/23

Citations

• Algorithm 245: Treesort
• Algorithm 230: Matrix Permutation

Cited by

• 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)
• In-place Heap Construction with Optimized Comparisons, Moves, and Cache Misses
• Average-case results on heapsort
• Heapsort [wikipedia]