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.

### 713. `sort()` complexity is too lax

Section: 25.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 25.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.266)

> 266) If the worst case behavior is important `stable_sort()` (25.3.1.2) or `partial_sort()` (25.3.1.3) should be used.