I agree, but you have to jump all over your data when you do a heapsort, blowing your cache.

It has nice worst-case guarantees, but a well-implemented quicksort has good cache locality.