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?
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})$.