The tl;dr is that for many use cases, you can get order of magnitude improvements by optimizing constant factors. In their case, they made a disk optimized vers

The tl;dr is that for many use cases, you can get order of magnitude improvements by optimizing constant factors. In their case, they made a disk optimized version of a binary heap by gathering nodes into pages. This is better because it's faster to read one 4kb page from disk, than it is to perform multiple 64b reads from disk. I think what's even more interesting are cases where algorithms with worse asymptotic complexity perform better than algorithms with a better asymptotic complexity. You see this all the time in the database world, since you are often better off optimizing for disk operations than for pure asymptotic complexity. The main example that comes to mind is that if you are performing a GROUP BY on a dataset that won't fit in memory, it's usually faster to calculate the GROUP BY with mergesort than it is with a hash-table. Hash tables are notoriously bad for disk performance. Every lookup or insert becomes one disk read or write. This is in contrast to mergesort where you can take two sorted files, and in one pass merge the two files together. This leads to a much smaller total number of disk reads and writes. Two other cases like this that come to mind are Fibonacci heaps vs binary heaps[0] and matrix multiplication algorithms[1]. [0] https://en.wikipedia.org/wiki/Fibonacci_heap#Practical_considerations https://en.wikipedia.org/wiki/Fibonacci_heap#Practical_consi... [1] https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_a...