I'm going to reply because you read the comments as I requested and I appreciate that. I don't have much time so this will be brief. Here's an extract from the

I'm going to reply because you read the comments as I requested and I appreciate that. I don't have much time so this will be brief. Here's an extract from the comments which actually says it well: <<< The claim "an algorithm that has been on the books as "optimal" for 46 years, which has been analyzed in excruciating detail by geniuses like Knuth and taught in all computer science courses in the world, can be optimized to run 10 times faster" is half wrong and half obvious. [which is what people here too have been saying] Is half wrong because you cannot talk about optimizing an algorithm in terms of "time", you can optimize its asymptotic computational complexity number of steps, which you did not. Is half obvious because the fact that heaps do not match well with virtual memory, with caches and with multiple execution pipelines in modern CPUs is something known since decades. [repeating what people have said here too, that once you have caches, memory accesses become very inconsistent. The time difference between a L1 cache hit and a main mem access can be 50 times, or even more. So much more than a single order of magnitude speed difference. If it hits disk via VM, OMG IT HURTS IT HURTS... That's why an 'inferior' algorithm that uses memory in a nice way can beat a technically superior algo that doesn't] Who decided to use a pure heap in that code was not a very good programmer, you proved to be a better one [I agree here], you did not change a little bit in the history of algorithms, a good CS class may help you about the fact that you think and claim you did, there is a long way before being able to even name Knuth. >>> Analysing algorithms can't AFAIK take into account much about caches. It's just too difficult. So analysis is valuable but limited (though with very important real-world value), and you need also to account for the fact that cache/VM effects are huge. The author didn't discover anything we - or you - aren't aware of, and he presented it badly. HTH