Not sure how you find this as O(n^2). It's clearly the divide and conquer version with O(n lg n) expected time. The only asymptotic complexity issue of the algo

Not sure how you find this as O(n^2). It's clearly the divide and conquer version with O(n lg n) expected time. The only asymptotic complexity issue of the algorithm is that it doesn't randomly pick p, so it will get O(n^2) perf on an already sorted list. It would be expected that you randomly shuffle a list before using this quicksort alg. When the author says this is not the true quicksort, he's referring to the fact that it needs O(n) auxiliary memory, because it's not swapping values in place (the real cost here is worse caching performance). It's definitely not an O(n^2) algorithm though.