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

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

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

 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.

 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.