It sets a stack limit proportional to log(n) and gives up and heapsorts the subproblem if the limit is exceeded. You get no more than n log(n) quicksort operations, plus heapsorting any partition of the input which is also n log(n)

In other words, they use the worst-case n log(n) heapsort with an optimization to use the much faster quicksort for non-pathological inputs, which is almost always.

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)