This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of CD1 status.
Section: 220.127.116.11 [sort] Status: CD1 Submitter: Matt Austern Opened: 2007-08-30 Last modified: 2016-01-28
Priority: Not Prioritized
View all issues with CD1 status.
The complexity of sort() is specified as "Approximately N log(N) (where N == last - first ) comparisons on the average", with no worst case complicity specified. The intention was to allow a median-of-three quicksort implementation, which is usually O(N log N) but can be quadratic for pathological inputs. However, there is no longer any reason to allow implementers the freedom to have a worst-cast-quadratic sort algorithm. Implementers who want to use quicksort can use a variant like David Musser's "Introsort" (Software Practice and Experience 27:983-993, 1997), which is guaranteed to be O(N log N) in the worst case without incurring additional overhead in the average case. Most C++ library implementers already do this, and there is no reason not to guarantee it in the standard.
In 18.104.22.168 [sort], change the complexity to "O(N log N)", and remove footnote 266:
ApproximatelyN log(N) (where N == last - first ) comparisons on the average. 266)
266) If the worst case behavior is important stable_sort() (22.214.171.124) or partial_sort() (126.96.36.199) should be used.