# Average case lower bound for sorting

The $\Omega(n\lg{n})$ lower bound for sorting in the comparison model is well known. Is there a similar average case lower bound for sorting in the comparison model and if so, which random distributions does it apply to?

• You might want to look up Kolmogorov complexity, and more specifically average case analysis done with the incompressibility method. (It's a general proof method based on KC and random strings). – Juho Apr 11 '15 at 16:22

In the Sedgewick-Bentley talk "QUICKSORT IS OPTIMAL" they give an (informal) proof that Quicksorts average case is optimal.

So the average case lower bound for sorting is $\Omega(n\lg{n})$.

• By average case I mean over random input distributions. I think you are referring to the average run time of a randomised algorithm which is something different. – Lembik Apr 11 '15 at 17:20
• @Lembik This is average case analysis over uniform input distributions. – orlp Apr 11 '15 at 17:23
• That's a very nice reference. Thank you. "The average number of compares per element C/N is always within a constant factor of the entropy H" – Lembik Apr 11 '15 at 17:28