BOTTOM-UP-HEAPSORT, A NEW VARIANT OF HEAPSORT BEATING, ON AN AVERAGE,QUICKSORT - (IF N IS NOT VERY SMALL)

Authors
WEGENER I
Citation
I. Wegener, BOTTOM-UP-HEAPSORT, A NEW VARIANT OF HEAPSORT BEATING, ON AN AVERAGE,QUICKSORT - (IF N IS NOT VERY SMALL), Theoretical computer science, 118(1), 1993, pp. 81-98
Citations number
18
Categorie Soggetti
Computer Sciences","Computer Applications & Cybernetics",Mathematics
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
118
Issue
1
Year of publication
1993
Pages
81 - 98
Database
ISI
SICI code
0304-3975(1993)118:1<81:BANVOH>2.0.ZU;2-W
Abstract
A variant of HEAPSORT, called BOTTOM-UP-HEAPSORT, is presented. It is based on a new reheap procedure. This sequential sorting algorithm is easy to implement and beats, on an average, QUICKSORT if n greater-tha n-or-equal-to 400 and a clever version of QUICKSORT (where the split o bject is the median of 3 randomly chosen objects) if n greater-than-or -equal-to 16 000. The worst-case number of comparisons is bounded by 1 .5n log n + 0(n). Moreover, the new reheap procedure improves the dele te procedure for the heap data structure for all n.