10

Since C++11, the C++ Standard Library (c.f. Section 25.4.1.1 of a draft verion of the standard) requires the std::sort algorithm to have asymptotic worst case execution time O(n log n) instead of average case.

Following the change, for example the quicksort algorithm does not comply the specification anymore. This was pointed out in a bugreport for LLVM's libc++. Instead, the algorithms introsort or pdqsort, which have worst case running time O(n log n), are used usually.

Is there any documentation on the motivation for that change? Is there some anecdote or incident that lead to that change?

Max Haslbeck
  • 151
  • 4
  • 2
    Because it can I guess. Why ask for less when you can ask for more? – n. m. could be an AI Mar 17 '21 at 09:00
  • where can I find the standard or a draft thereof? – Max Haslbeck Mar 17 '21 at 09:02
  • @MaxHaslbeck I use this site [https://github.com/timsong-cpp/cppwp](https://github.com/timsong-cpp/cppwp) – Quimby Mar 17 '21 at 09:03
  • 1
    https://stackoverflow.com/questions/81656/where-do-i-find-the-current-c-or-c-standard-documents – underscore_d Mar 17 '21 at 09:03
  • 9
    Indepentently of the actual reasons: Specifying the worst case is formally stronger than solely specifying the average case in terms of algorithm robustness. – Secundi Mar 17 '21 at 09:11
  • @Secundi I think intuitively you are right. For your claim it is important which kind of distribution of input arrays is used to determine the average case complexity of a sorting algorithm. I think it might be hard to prove your claim rigorously. :) – Max Haslbeck Mar 17 '21 at 09:14
  • No, that isn't the question. It *was* the question, until C++11 got rid of it. – user207421 Mar 17 '21 at 09:18
  • @MaxHaslbeck did you misread Secundis comment? It is in line with the point you raise. Making a statement about worst case is stronger than making a statement for average case, also for the reason you mention – 463035818_is_not_an_ai Mar 17 '21 at 09:19
  • Well, in the linked resources I can nowhere see "worst case". Is it implied? Or is it poor wording? – Tobias Brösamle Mar 17 '21 at 09:24
  • @TobiasBrösamle complexity must always be same or better than specified (so yes it is implicit), while average means that it can be worse for specific cases – 463035818_is_not_an_ai Mar 17 '21 at 09:27
  • @largest_prime_is_463035818 I guess I misread. @Secundi pointed out an important aspect. Sorry for diverting the discussion. I'd like to focus on the motivation for the change. Were there maybe some DoS attacks exploiting some patterns that made `std::sort` quadratic? – Max Haslbeck Mar 17 '21 at 09:28
  • @TobiasBrösamle in that document (I think) "average case" is noted explicitely and if not explicitely stated "worst case" is considered – Max Haslbeck Mar 17 '21 at 09:29
  • no, well I am sorry for interfering. Question is clear enough, we just have to wait for someone to know the answer and write it down :) – 463035818_is_not_an_ai Mar 17 '21 at 09:30
  • 2
    The the 1998 standard probably specified O(n log n) average complexity because algorithms offering that were relatively mature, while sorting algorithms with O(n log n) WCET were less so (e.g. introsort was created in 1997). In 2011, more algorithms with O(n log n) WCET would have been available and mature, so the standard could be updated. That lag is normal, and allows for rigorous verification of claims about the performance of algorithms (rather than introducing and later having to retrospectively remove a requirement because it is found that claims about newer algorithm don't hold up) – Peter Mar 17 '21 at 09:53
  • The 1999 STL documentation from SGI contains a [note about adopting Introsort](https://justinmeiners.github.io/sgi-stl-docs/sort.html#2) but doesn't give an exact date. – Blastfurnace Mar 17 '21 at 10:48
  • It's not surprising that Introsort was adopted into some implementation of the STL fairly early because David Musser and Alex Stepanov had collaborated on generic programming since the 1980s. – Blastfurnace Mar 17 '21 at 11:11
  • Demo of quadratic number of operation in Clang's `std::sort` (from the bug report): https://gcc.godbolt.org/z/KdfT3rY1K – Fedor Oct 15 '21 at 06:47
  • This is issue 713 of the standard library [here](https://www.open-std.org/JTC1/sc22/wg21/docs/papers/2008/n2577.html). – n. m. could be an AI Dec 18 '22 at 19:33

0 Answers0