713. sort() complexity is too lax

Section: 26.8.2.1 [sort] Status: CD1 Submitter: Matt Austern Opened: 2007-08-30 Last modified: 2016-01-28

Priority: Not Prioritized

View all issues with CD1 status.

Discussion:

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.

Proposed resolution:

In 26.8.2.1 [sort], change the complexity to "O(N log N)", and remove footnote 266:

Complexity: Approximately O(N log(N)) (where N == last - first ) comparisons on the average.²⁶⁶⁾

²⁶⁶⁾ If the worst case behavior is important stable_sort() (25.3.1.2) or partial_sort() (25.3.1.3) should be used.