Well, Quick Sort is O(n log n) on average, but you know that. Also, anything that's O(n log n) is also O(n^2), which means that the author is the worst kind of correct -- but you knew that too :)