# 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.

### See also

`stable_sort`, `partial_sort`, `partial_sort_copy`, `sort_heap`, `is_sorted`, `binary_search`, `lower_bound`, `upper_bound`, `less<T>`, StrictWeakOrdering, LessThan Comparable

Copyright © 1999 Silicon Graphics, Inc. All Rights Reserved. TrademarkInformation