 

Category: algorithms   Component type: function 
Prototype
Sort
is an overloaded name; there are actually two sort
functions.
template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering>
void sort(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering comp);
Description
Sort
sorts the elements in [first, last)
into ascending order, meaning that if i
and j
are any two valid iterators in [first, last)
such that i
precedes j
, then *j
is not less than *i
. Note: sort
is not guaranteed to be stable. That is, suppose that *i
and *j
are equivalent: neither one is less than the other. It is not guaranteed that the relative order of these two elements will be preserved by sort
. [1]
The two versions of sort
differ in how they define whether one element is less than another. The first version compares objects using operator<
, and the second compares objects using a functors comp
.
Definition
Defined in the standard header algorithm, and in the nonstandard backwardcompatibility header algo.h.
Requirements on types
For the first version, the one that takes two arguments:

RandomAccessIterator
is a model of RandomAccessIterator.

RandomAccessIterator
is mutable.

RandomAccessIterator
's value type is LessThanComparable.

The ordering relation on
RandomAccessIterator
's value type is a strict weak ordering, as defined in the LessThanComparable requirements.
For the second version, the one that takes three arguments:

RandomAccessIterator
is a model of RandomAccessIterator.

RandomAccessIterator
is mutable.

StrictWeakOrdering
is a model of StrictWeakOrdering.

RandomAccessIterator
's value type is convertible to StrictWeakOrdering
's argument type.
Preconditions

[first, last)
is a valid range.
Complexity
O(N log(N))
comparisons (both average and worstcase), where N
is last  first
. [2]
Example
int A[] = {1, 4, 2, 8, 5, 7};
const int N = sizeof(A) / sizeof(int);
sort(A, A + N);
copy(A, A + N, ostream_iterator<int>(cout, " "));
Notes
[1] Stable sorting is sometimes important if you are sorting records that have multiple fields: you might, for example, want to sort a list of people by first name and then by last name. The algorithm stable_sort
does guarantee to preserve the relative ordering of equivalent elements.
[2] Earlier versions of sort
used the quicksort algorithm (C. A. R. Hoare, Comp. J. 5, 1962), using a pivot chosen by median of three (R. C. Singleton, CACM 12, 1969). Quicksort has O(N log(N))
average complexity, but quadratic worstcase complexity. See section 5.2.2 of Knuth for a discussion. (D. E. Knuth, The Art of Computer Programming. Volume 3: Sorting and Searching. AddisonWesley, 1975.) The current implementation of sort
, however, uses the introsort algorithm (D. R. Musser, "Introspective Sorting and Selection Algorithms", Software Practice and Experience 27(8):983, 1997.) whose worst case complexity is O(N log(N))
. Introsort is very similar to medianofthree quicksort, and is at least as fast as quicksort on average.
See also
stable_sort
, partial_sort
, partial_sort_copy
, sort_heap
, is_sorted
, binary_search
, lower_bound
, upper_bound
, less<T>
, StrictWeakOrdering, LessThanComparable