Ironically, quicksort performs the worst when an array is already sorted, assuming we use the pivot element selection as in listing 2. This is because element a[e] is already at the right place. This makes the pivot p′ = e, and thus the recursive call needs to handle elements from index 0 to e − 1. In other words, each recursion only reduces the array segment by one element.
As a result, the algorithm needs to call itself recursively n − 1 times. This make the time complexity O(n2).