I know this is nitpicky, but quicksort is, worst-case, O(n^2), meaning a large number of comparison based sorting algorithms are faster than it. Its in the average case that Quicksort wins.
Even though other algorithms such as Mergesort also have O(nlogn), Quicksort is normally the preferred implementation because it's relatively easy to do in-place and generally is the most efficient[1] of all the sorting algorithms.
[1]Not my field of expertise though, happy to be told I'm wrong.
To pick that part, first you write your (randomized) QuickSort, then your antagonists picks the worst case, and last you let your algorithm run and pick its random numbers. No matter how the antagonist chooses the input (but not the random numbers), you get O (n log n) expected runtime.
This is different from an average (over all inputs) run time.
This is the beauty of randomized analysis in the worst-cases. The worst-case occurs if and only if the random generator spits out a sorted list. If all permutations are equally likely, a list of n elements has probability 1/n! of coming out sorted = O(n^2).
Even in practice, this is very pessimisstic as it only occurs with a probability of 1/n! and is therefore extremely rare.
"... given a worst-case O(n) selection algorithm, one can use it to find the ideal pivot (the median) at every step of quicksort, producing a variant with worst-case O(n log n) running time. In practical implementations this variant is considerably slower on average, but it is of theoretical interest, showing how an optimal selection algorithm can yield an optimal sorting algorithm."
https://en.wikipedia.org/wiki/Quicksort#Selection-based_pivo...
This optimization is useful in practice. The result is a sort that is as fast as Quicksort on average, but unlike Quicksort runs in O(n log n) time. So, for example, the C++ Standard Library function std::sort will use Introsort in any good implementation.
Despite its wonderfulness, Introsort is strangely little known. Algorithms texts rarely mention it, for some reason.
If you are interested in theory, the pivot in linear time algorithm (like QuickSelect) is truly marvelous. It also provides a good study of how simple a randomized algorithm can be, and how to de-randomize it into something much more complicated but deterministic. But in some sense that complications help you understand, because otherwise, randomize algorithms are often `magic'.
Anyway, slightly modified my point still stands: BFPRT is way more complicated (and harder to come up with) than randomized QuickSelect.