Every ref to quicksort worth its salt mentions that it is O(n log n) average case, and O(n^2) worst case.

The problem with "average case" analysis is that you must give your assumptions; Without precisely stating your assumptions, "average case" is useless.