https://gcc.gnu.org/bugzilla/show_bug.cgi?id=35968
--- Comment #14 from Stephen Howe <sjhowe at dial dot pipex.com> --- (In reply to Anders Kaseorg from comment #13) > (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. I am the original bug reporter. The C++ standard is not good enough for this algorithm. In David Musser's original paper http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.5196&rep=rep1&type=pdf he describes Introsort, and in the ISO C++ 2011 standard, the complexity requirements tightened for std::sort() from O(n * log n) on average, to O(n * log n) in the worse case. Introsort guarantees that. It uses quicksort unless it detects that pivot selection is going bad for portions of the array, it which case it uses heapsort for which has no known worse case. So guaranteed worse case performance. Now David Musser also wrote about intraselect which analogously uses quickselect but his paper did not say which algorithm should be swapped to if quickselect went bad. The median-of-medians (in at least groups of 5) is such an algorithm with O(n) performance. Heapselect is not O(n). So the C++ standard could use Intraselect with guaranteed O(n) performance, not just on average. The big O complexity could be tightened up in the same way that std::sort() was tightened up in ISO C++ 2011. > Quickselect with randomized Θ(1) pivot selection No. It can be beaten. Even randomized Θ(1) pivot selection is not good enough. Antiqsort by Doug McIlroy can beat it. See https://www.cs.dartmouth.edu/~doug/aqsort.c Cheers Stephen Howe
