sort


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 function object comp.

Definition

Defined in the standard header algorithm and in the nonstandard backward-compatibility header algo.h.

Requirements on types

For the first version the one that takes two arguments:

RandomAccessIterator is a model of Random Access Iterator.
RandomAccessIterator is mutable.
RandomAccessIterator's value type is LessThan Comparable.
The ordering relation on RandomAccessIterator's value type is a strict weak ordering as defined in the LessThan Comparable requirements.

For the second version the one that takes three arguments:

RandomAccessIterator is a model of Random Access Iterator.
RandomAccessIterator is mutable.
StrictWeakOrdering is a model of Strict Weak Ordering.
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 worst-case) 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
" "));
// The output is " 1 2 4 5 7 8".

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 worst-case complexity. See section 5.2.2 of Knuth for a discussion. (D. E. Knuth The Art of Computer Programming. Volume 3: Sorting and Searching. Addison-Wesley 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 median-of-three quicksort and is at least as fast as quicksort on average.