home

Heapsort Flavors20180628Have you ever loved an algorithm? Ever since my upper division Algorithms course in college, I have had a soft spot for heapsort  largely because it has predictable performance. It also has a pure elegance in the implementation. At least, as I remembered it... After some years away, I recently returned to it in an effort to burnish my slightly rusty memories regarding searching, sorting and data structures. Turns out that heapsort is introduced in multiple different ways. Skeina & CLR deliver a 3function heapsort combining makeheap and heapify, wrapped in heapsort. Knuth vol 3 delivers a 1function heapsort with a siftup subroutine (Algorithm H, section 5.2.3) Levitin, my college textbook, has a general twophase concept, but without being so precise as to offer pseudocode for it. Aho 74 indicates a 3function heapsort as well. What is peculiar is that my original implementation  circa 2005  uses a twofunction concept that is strikingly similar to Knuth  but I wasn't reading Knuth when I implemented it. Checking FreeBSD's heapsort  https://github.com/ddeville/libc/blob/master/src/stdlib/FreeBSD/heapsort.c#L132  we notice that it was derived from Knuth, but the installation of C macros makes the logic unclear. I may have derived the implementation from Baase 2nd ed, the only other book I believe I was using at the time, but slides derived from Baase don't appear to have the 1function siftup approach. Examining Wikipedia from winter 2005 reveals pseudocode strikingly similar to what I wrote. A little bit of Wikipedia walking reveals that the author eventually wound up as an engineer at Google. Regrettably, he didn't cite his pseudocode sourcing. The interesting question to me is how these variants have all sort of arrived in the literature as they did. I wonder which ones are actually better. I present, only tweaked to run in g++,
Enjoy! 