How can Timsort beat the O(n log n) sorting bound in some cases?

Question

I heard that Timsort breaks the O(n log n) bound for some cases taking advantages of data pattern. How it is possible? Can anyone explain me in detail? If it is true then Timsort will always take less comparison than quick sort because on real life data there is some pattern except data is truly random?

Can we use some kind of tricks to break O(n log n) bound on avg case for comparison sorts?

Answer 1

It depends on what you mean by average here. Within the field of CS, average has a very precise meaning: The mean over all possible input sets, assuming each possible input set has the same probability. This definition is convenient, because it's precise and quite easy to handle, but in some cases not the most useful one, because real word data typically is different from random numbers, so an arguably better definition of average would be: The mean over all real-world input sets. But this is not very precise and won't work in a scientific context, so you won't find this in academia. The difference of both definitions is huge: In real world data, you can reasonably assume that there is a fixed percentage K1 of input sets that can be sorted in linear time by something like timsort. For random data, the percentage K2(n) that can be sorted in linear time goes to zero very quickly, like K2=Exp(-n), with n being the size of the input set. So the precise, academic answer to you question is No, you cannot improve the average case. The answer from a real-world engineer would be Maybe, it depends, we can try. And they do.