A simplified complexity analysis of mcdiarmid and reed's variant of bottom-up-heapsort

DOI10.1080/00207160008804896zbMath0956.68038OpenAlexW2061153095MaRDI QIDQ4950608

Suman Kumar Nath, Mohammad Kaykobad, Rezaul Alam Chowdhury

Publication date: 9 April 2000

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207160008804896

zbMATH Keywords

fine heapMDR-HEAPSORT

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Data structures (68P05)

Related Items (1)

An in-place heapsort algorithm requiringnlogn+nlog*n−0.546871ncomparisons

Cites Work

• Unnamed Item
• Heaps with bits
• BOTTOM-UP-HEAPSORT, and new variant of HEAPSORT beating, on an average, QUICKSORT (if \(n\) is not very small)
• A variant of heapsort with almost optimal number of comparisons
• The worst case complexity of McDiarmid and Reed's variant of BOTTOM-UP HEAPSORT is less than \(n \log n+1.1n\)
• Heaps on Heaps
• Building heaps fast

This page was built for publication: A simplified complexity analysis of mcdiarmid and reed's variant of bottom-up-heapsort