[elwes5]

Big O gets you in the right ballpark of what to look at. That extra 'C' bit that gets left out can doom it to be worse than other items though.

For example for very small sets of numbers you could basically pre-sort every combination there is then have a very large lookup table. Much like a rainbow table for passwords. Your O is basically a binary search lookup O(log(n)) or even better O(1) if you can make it linear. However, the upfront cost is huge and storage cost is huge, lookup would probably be big too. Hmm, now that I think about it this could be an interesting thing to mess with. Also at this time anything past 4 bytes would be unusable. Hmm, maybe later. Like you point out a 'galactic alg'. Portions of that thinking can be pulled out and used for other items though.

With sorting using the comparison is a good proxy for if it might perform well. But it is just that, a proxy. Like the weird sort I just made up. There is probably a few shifts and muls in there. Those are decently expensive and can blow your perf right out of the water.

[MaxBarraclough]

> Big O gets you in the right ballpark of what to look at

Generally I'd say that's true, but even that depends on context. For sorting very small arrays, on typical hardware, you can't beat bubble-sort and insertion-sort.

[elwes5]

Oh absolutely. The bubble sort sort thing usually comes down to the architecture of the machine. One of the things the O notation kind of hand waves away. On paper some things are faster. But put in 3 levels of cache, a CPU scheduler, a particular ASM instruction flow that makes things faster/slower and suddenly things are different. That is my biggest gripe with the notation. It is good to get you 'close'. But sometimes you just need to fiddle with it and try it. The 'C' bit can get you. On paper bubble sort is always worse. But it can run faster for small sets because the code and is small enough to fit into L1. Whereas maybe a mergesort implementation either the code or the data fits but not both.