I may have oversold Sedgewick's claim: he doesn't actually say that a properly implemented quicksort will never go quadradic; only that "The average number of

I may have oversold Sedgewick's claim: he doesn't actually say that a properly implemented quicksort will never go quadradic; only that "The average number of compares per element ... is always within a constant factor of the entropy" and "No comparison-based algorithm can do better" (page 16). I've never looked into whether a Sedgewick-approved Quicksort can avoid worst case behavior against antiquicksort ( http://www.cs.dartmouth.edu/~doug/aqsort.c http://www.cs.dartmouth.edu/~doug/aqsort.c , http://www.cs.dartmouth.edu/~doug/mdmspe.pdf http://www.cs.dartmouth.edu/~doug/mdmspe.pdf ).