Quicksort, Heapsort, Fast Heapsort, and Entropy

Rated 5 stars out of 5.

In asking why Heapsort works using twice the comparisons of Quicksort but in practice works 20% faster and yet both scale N·log·N on average, David Mackay uses entropy to tweak it and devise a simple and clever sort yet even closer to the information theoretic optimum: Fast Heapsort. He also suggests improvements to Quicksort, and poses a simple puzzle to convey why using entropy works better.