I was unable to find a general purpose implementation of bottom-up heapsort, so I've made it myself, with a little modification.
You can find the source code on Github: github.com/Maxime2/heapsort
Bottom-up heapsort (bottom-up-heapsort) is a variant of heapsort with a new reheap procedure. This sequential sorting algorithm beats, on an average, quicksort if n > 2400 and a clever version of quicksort (median-3 modification) if n > 16000.
The algorithm of bottom-up heapsort is described in Ingo Wegener, BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT beating, on an average, QUICKSORT (if n is not very small), Theoretical Computer Science 118 (1993), pp. 81-98, Elsevier.
The modification I've made saves (n-2)/2 swaps and (n-2)/2 comparisons, for n > 3. It is based on the idea of delayed reheap after moving the root to its place from D. Levendeas, C. Zaroliagis, Heapsort using Multiple Heaps, in Proc. 2nd Panhellenic Student Conference on Informatics -- EUREKA. – 2008. – P. 93–104.
Pingback: dpsearch-4.54-2013-09-15 | Founds
Have you considered adding this to ccan (http://ccodearchive.net/)?
Hi!
I know this is probably old history for you but I have a question about your heapsort. I am not very familiar with C so when I looked at your code, I could not understand what parameters I should call the routine with.
Clearly it is called with heapsort(vbase, nmemb, size, compar) but what are vbase, nmemb, size, compar??
I hope that you can let me know - the algorithm looks interesting 🙂
Regards,
Pete
Hi Pete,
The meaning of vbase, nmemb, size and compar is desciped in man pages for heapsort function: man heapsort