https://gcc.gnu.org/bugzilla/show_bug.cgi?id=35968
--- Comment #13 from Anders Kaseorg <andersk at mit dot edu> --- (In reply to Patrick J. LoPresti from comment #12) > I am familiar with the usual algorithmic complexity definitions. > > So, just to be clear... Your assertion is that the C++ standards committee > adopted a specification that rules out a deterministic implementation? I should have been clearer: I’m saying it rules out quickselect with a deterministic pivot selection rule that doesn’t inspect Θ(n) elements. Quickselect with randomized Θ(1) pivot selection would satisfy the specification, as would quickselect with deterministic Θ(n) pivot selection by median-of-medians or similar, but not quickselect with deterministic Θ(1) pivot selection by taking the first element or similar.
