Well, Tarjan developed an O(n) worst-case order statistics algorithm, which you could use to implement exact pivot selection and partitioning in O(n) time. The constant factors would be horrid, but it would be a valid implementation of quicksort with a worst-case running time of O(n log n)