Among the day’s mysteries is how, despite having a long list of things to do, I found myself reading the Wikipedia entry on heap sort. Which leads to an admission: I never really “got” heap sort.
Back when I was studying the basic sorting algorithms, I passed heap sort over in favor of order preserving sorts like bubble sort, quick merge sort, and that great bar bet winner when you’re arguing with someone who insists that O(n log n) time is the best you can do, radix sort. Heap sort struck me as taking a lot of haphazard swapping to achieve a result that didn’t preserve order, and most of the sorting I needed to do required preserving order. So, bye bye heap sort.
Since then, there’s been no reason to revisit the issue. When I count the number of times in the last decade that I’ve coded up a sort routine, I don’t even have to use any fingers. The built-in sort in whichever language I’ve been coded with has always been good enough for the problem at hand. I’ve reinvented plenty of other wheels, but never sorting.
So why, when there’s work to do, spend a half-hour puzzling through the heap sort algorithm? Damn good question. Stumbling on a reference to it might have tweaking some latent guilt (of the “I made it through College without ever having read <pick a classic>, and one day they might find out and revoke my diploma” variety). Or maybe I was bored and needed a shot of intellectual stimulation. Grokking heap sort is a bit of a challenge. It strikes me as the type of algorithm that was dreamed up by someone whose idea of fun is figuring out ways to do long sequence of captures in checkers.
Was it worth the time? I think so. I may never need a heap sort, but the form of the algorithm is a good reminder that two-pass attacks, where the first pass does some non-immediately-obvious setup that the second pass can exploit, can be effective against some problems.
A reader kindly pointed out that I had my sorts confused, and that it’s mergesort that preserves order, not quicksort. I rechecked, and yup, I’d gotten them backwards.