# 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

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