**Section:** 27.8.2.1 [sort] **Status:** CD1
**Submitter:** Matt Austern **Opened:** 2007-08-30 **Last modified:** 2016-01-28 10:19:27 UTC

**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 27.8.2.1 [sort], change the complexity to "O(N log N)", and remove footnote 266:

Complexity:~~Approximately~~O(Nlog(N)) (whereN==last-first) comparisons~~on the average~~.^{266)}

^{266)}If the worst case behavior is importantstable_sort()(25.3.1.2) orpartial_sort()(25.3.1.3) should be used.