Nice meditation kyle.

While reading it I was reminded of a rather interesting thread on p5p regarding heap sort.

Short summary: some research folks found that they could reduce the number of comparisons in heapsort. John P. Linderman answered that it's all fine and good, but in real life heapsort suffers from bad caching characteristics, and thus can't really compete with mergesort and quicksort.

Still it's a very nice technique, and I could imagine that heapsort beats other algorithms when you only need to sort half of the list. (Maybe you could also optimize quicksort to only find the median - any thoughts on that?)