Proposed resolution:

In [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.

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.