Heapsort is useless in real world...
Posted Jan 12, 2012 9:32 UTC (Thu) by khim
In reply to: Worst case performance and "impossibly unlikely" conditions
Parent article: Denial of service via hash collisions
Heapsort is only good for things like priority_queue. The fact that it does not use additional memory looks good on paper but in reality it's red herring. The problem with heapsort is that it uses pathological memory access patters which make it literally hundreds of times slower once your heap is larger then your L3 cache (end it's significantly slower then merge sort when you overflow L1).
This means that there are only two cases where heapsort is good:
1. When data is small enough to fit in L1 cache.
2. When you have just enough data to fit in memory (L2 cache, L3 cache, etc), but there are not enough memory to keep second copy.
In first case mergesort is worse but still acceptable and second case is extremely rare (unless your program is designed to behave this way) thus heapsort is obviously very poor default.
to post comments)