
ALINK="#ff0000">
sort
PrototypeSort 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); DescriptionSort 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. DefinitionDefined in the standard header algorithm, and in the nonstandard backwardcompatibility header algo.h.Requirements on typesFor the first version, the one that takes two arguments:
Preconditions
ComplexityO(N log(N)) comparisons (both average and worstcase), where N is last  first. [2]Exampleint 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 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 alsostable_sort, partial_sort, partial_sort_copy, sort_heap, is_sorted, binary_search, lower_bound, upper_bound, less<T>, StrictWeakOrdering, LessThan ComparableCopyright © 1999 Silicon Graphics, Inc. All Rights Reserved. TrademarkInformation
