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-YzbMath0783.68060WikidataQ56049337 ScholiaQ56049337MaRDI QIDQ688722

Ingo Wegener

Publication date: 12 December 1993

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

zbMATH Keywords

quicksortaverage case analysis of algorithmsheapsort

Mathematics Subject Classification ID

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

Related Items (14)

An in-place heapsort algorithm requiringnlogn+nlog*n−0.546871ncomparisons ⋮ Optimizing binary heaps ⋮ Weak heaps engineered ⋮ The worst case complexity of McDiarmid and Reed's variant of BOTTOM-UP HEAPSORT is less than \(n \log n+1.1n\) ⋮ Heaps with bits ⋮ QuickHeapsort: modifications and improved analysis ⋮ STRONGER QUICKHEAPS ⋮ Sorting using heap structure ⋮ Multiway in-place merging ⋮ On sorting, heaps, and minimum spanning trees ⋮ A simplified complexity analysis of mcdiarmid and reed's variant of bottom-up-heapsort ⋮ QuickXsort: a fast sorting scheme in theory and practice ⋮ FAT HEAPS WITHOUT REGULAR COUNTERS ⋮ QuickHeapsort, an efficient mix of classical sorting algorithms

Uses Software

• Quicksort

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Average-case results on heapsort
• A variant of heapsort with almost optimal number of comparisons
• Deleting the root of a heap
• The analysis of Quicksort programs
• An average case analysis of Floyd's algorithm to construct heaps
• Building heaps fast
• Increasing the efficiency of quicksort
• 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)