[enedil]

O(n lg n) is indeed hard to prove for quicksort, because it is not even true in the general case. Worst case is O(n^2).