[dekhn]

quicksort is O(nlogn) average case, and O(n2) on already sorted arrays.

[bvinc]

Just a nitpick: There are versions of quicksort that perform well, O(n*log n), on already sorted data. But there is always some worst case scenario where it can be O(n^2).