Section: 188.8.131.52 [sort] Status: CD1 Submitter: Matt Austern Opened: 2007-08-30 Last modified: 2016-02-10
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 184.108.40.206 [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() (220.127.116.11) or partial_sort() (18.104.22.168) should be used.