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 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", 1997. To be published in Software Practice and Experience.) 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.