> Now and long the usual criterion of performance is big-O notation, and that is what I considered, with the Gleason bound and heap sort and, thus, showed that,

> Now and long the usual criterion of performance is big-O notation, and that is what I considered, with the Gleason bound and heap sort and, thus, showed that, with various common assumptions, can't do better than heap sort. As far as I know, I was correct. That's a little short sighted for real life performance. Memory access patterns, cache performance, and the hidden constant factor are all relevant for real performance. For example there's a 200x difference between main memory and cache access times. log2(1000000000000) is ~40, meaning poor cache performance can impact performance by more than a factor of log(n) in the Big-O notation. There are also many cases where algorithms with better Big-O performance have constant factors so large that they perform worse for common problem sizes. Matrix multiplication is a good example. Strassen's algorithm has a better Big-O than the straightforward algorithm, but the constant factor is large enough that it only becomes faster on matrices larger than maybe 100x100. And there are algorithms even better than Strassen's, but their constant factors are so big they're effectively never better than Strassen's on real hardware.