%0 Journal Article %1 BottomUpHeapsort %A Wegener, Ingo %D 1993 %J Theoretical Computer Science %K 2011 algorithm heapsort kde quicksort seminar sorting %N 1 %P 81 - 98 %R 10.1016/0304-3975(93)90364-Y %T BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT beating, on an average, QUICKSORT (if n is not very small) %U http://www.sciencedirect.com/science/article/pii/030439759390364Y %V 118 %X 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 ngreater-or-equal, slanted400 and a clever version of QUICKSORT (where the split object is the median of 3 randomly chosen objects) if ngreater-or-equal, slanted16000. The worst-case number of comparisons is bounded by 1.5n log n+O(n). Moreover, the new reheap procedure improves the delete procedure for the heap data structure for all n.

@article{BottomUpHeapsort, 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-or-equal, slanted]400 and a clever version of QUICKSORT (where the split object is the median of 3 randomly chosen objects) if n[greater-or-equal, slanted]16000. The worst-case number of comparisons is bounded by 1.5n log n+O(n). Moreover, the new reheap procedure improves the delete procedure for the heap data structure for all n.}, added-at = {2011-06-21T22:52:29.000+0200}, author = {Wegener, Ingo}, biburl = {https://www.bibsonomy.org/bibtex/299f1ffe7091a547a5b1b4dc6f12a6a0c/mwetzel}, description = {ScienceDirect - Theoretical Computer Science : BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT beating, on an average, QUICKSORT (if n is not very small)}, doi = {10.1016/0304-3975(93)90364-Y}, interhash = {1876a3b7aac290a08d7c855e50bcdfef}, intrahash = {99f1ffe7091a547a5b1b4dc6f12a6a0c}, issn = {0304-3975}, journal = {Theoretical Computer Science}, keywords = {2011 algorithm heapsort kde quicksort seminar sorting}, number = 1, pages = {81 - 98}, timestamp = {2011-06-21T23:42:28.000+0200}, title = {BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT beating, on an average, QUICKSORT (if n is not very small)}, url = {http://www.sciencedirect.com/science/article/pii/030439759390364Y}, volume = 118, year = 1993 }