Hacker News Reader

You can implement merge sort in place too:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22....

Looks like the algo is more complicated, but surely implementable. In most modern architectures, the key for performance is how one exploits the caching behavior. Quicksort is very cache friendly, as well as the common implementation of merge sort. Not so for heapsort.

"The O(n) extra-space required by mergesort isn't always available."

Heapsort

No, but mergesort can easily fall back to dumping its sorted contents to disk, for later merging; this disk-based merge sort was invented by van Neumann in the 1940s, and is how the unix utility sort works (dozen-way merge of sorted shards of a file).

Mergesort gets pretty damn efficient, even with moderate buffer space.