BOTTOM-UP-HEAPSORT, and new variant of HEAPSORT beating, on an average, QUICKSORT (if n is not very small)

DOI10.1016/0304-3975(93)90364-YMaRDI QIDQ688722zbMATHWikidataFDO

Authors Ingo Wegener

Publication date 12 December 1993

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

quicksortheapsortaverage case analysis of algorithms

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4213429
• The worst case complexity of McDiarmid and Reed's variant of BOTTOM-UP HEAPSORT is less than \(n \log n+1.1n\)
• A variant of heapsort with almost optimal number of comparisons
• A simplified complexity analysis of mcdiarmid and reed's variant of bottom-up-heapsort

Cites work

• scientific article; zbMATH DE number 4213429 (Why is no real title available?)
• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• scientific article; zbMATH DE number 176500 (Why is no real title available?)
• A variant of heapsort with almost optimal number of comparisons
• An average case analysis of Floyd's algorithm to construct heaps
• Average-case results on heapsort
• Building heaps fast
• Deleting the root of a heap
• Increasing the efficiency of quicksort
• Quicksort
• The analysis of Quicksort programs

Cited in

(16)

• The worst case complexity of McDiarmid and Reed's variant of BOTTOM-UP HEAPSORT is less than \(n \log n+1.1n\)
• A simplified complexity analysis of mcdiarmid and reed's variant of bottom-up-heapsort
• Multiway in-place merging
• Heap construction: Optimal in both worst and average cases?
• Fat heaps without regular counters
• Weak heaps engineered
• STRONGER QUICKHEAPS
• QuickHeapsort, an efficient mix of classical sorting algorithms
• scientific article; zbMATH DE number 176500 (Why is no real title available?)
• A lower bound for the worst case of bottom-up-heapsort
• On sorting, heaps, and minimum spanning trees
• Sorting using heap structure
• Heaps with bits
• QuickXsort: a fast sorting scheme in theory and practice
• Optimizing binary heaps
• An in-place heapsort algorithm requiringnlogn+nlog*n−0.546871ncomparisons

Describes a project that uses

Uses Software

• Quicksort

This page was built for publication: BOTTOM-UP-HEAPSORT, and new variant of HEAPSORT beating, on an average, QUICKSORT (if \(n\) is not very small)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q688722)