The worst case complexity of McDiarmid and Reed's variant of BOTTOM-UP HEAPSORT is less than \(n \log n+1.1n\)

DOI10.1016/0890-5401(92)90005-ZzbMath0766.68025WikidataQ56049342 ScholiaQ56049342MaRDI QIDQ1186810

Ingo Wegener

Publication date: 28 June 1992

Published in: Information and Computation (Search for Journal in Brave)

zbMATH Keywords

quicksortheapsortbottom-up heapsort

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Related Items

An In-Place Priority Queue with O(1) Time for Push and $$\lg n + O(1)$$ lg n + O ( 1 ) Comparisons for Pop, Optimizing binary heaps, Heaps with bits, Sorting using heap structure, A simplified complexity analysis of mcdiarmid and reed's variant of bottom-up-heapsort, The heap-mergesort, Weak-heap sort, QuickHeapsort, an efficient mix of classical sorting algorithms

Cites Work

• BOTTOM-UP-HEAPSORT, and new variant of HEAPSORT beating, on an average, QUICKSORT (if \(n\) is not very small)
• Average-case results on heapsort
• A variant of heapsort with almost optimal number of comparisons
• Deleting the root of a heap
• An average case analysis of Floyd's algorithm to construct heaps
• Building heaps fast