From cppreference.com
Defined in header
template<classRandomIt>voidsort(RandomItfirst,RandomItlast); (1)(constexpr since C++20)template<classRandomIt,classCompare>voidsort(RandomItfirst,RandomItlast,Comparecomp); (2)(constexpr since C++20)template<classExecutionPolicy,classRandomIt>voidsort(ExecutionPolicy&&policy,RandomItfirst,RandomItlast); (3) (since C++17)template<classExecutionPolicy,classRandomIt,classCompare>voidsort(ExecutionPolicy&&policy,RandomItfirst,RandomItlast,Comparecomp); (4) (since C++17)Sorts the elements in the target range [first, last). The order of equivalent elements is not guaranteed to be preserved.
1) Elements are
with respect to operator<(until C++20)std::less{}(since C++20).
2) Elements are sorted with respect to comp.
3,4) Same as (1,2), but executed according to policy.
These overloads participate in overload resolution only if the value of the following expression is true:
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>
(until C++20)std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>
(since C++20)If any of the following conditions is satisfied, the behavior is undefined:
Parameters
first, last - the pair of iterators defining the target
comp - comparison function object (i.e. an object that satisfies the requirements of
) which returns true if the first argument is less than (i.e. is ordered before) the second. The signature of the comparison function should be equivalent to the following:
boolcmp(constType1&a,constType2&b);
While the signature does not need to have const&, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) Type1 and Type2 regardless of
(thus, Type1& is not allowed, nor is Type1 unless for Type1 a move is equivalent to a copy(since C++11)).
The types Type1 and Type2 must be such that an object of type RandomIt can be dereferenced and then implicitly converted to both of them.
policy - the
to use Type requirements -RandomIt must meet the requirements of
. -Compare must meet the requirements of
. Complexity
Given N as last-first:
1,3)𝓞(N·log(N)) comparisons using operator<(until C++20)std::less{}(since C++20).
2,4)𝓞(N·log(N)) applications of the comparator comp.
Exceptions
3,4) During the execution process:
If the temporary memory resources required for parallelization are not available,
is thrown.
If an uncaught exception is thrown while accessing objects via an algorithm argument, the behavior is determined by the execution policy (for
,
is invoked).
Notes
Before
, the complexity requirement allowed sort() to be implemented using only
, which may need 𝓞(N2
) comparisons in the worst case.
can handle all cases with 𝓞(N·log(N)) comparisons (without incurring additional overhead in the average case), and thus is usually used for implementing sort().
libc++ has not implemented the corrected time complexity requirement
.
Possible implementation
See also the implementations in
and
.
Example
Run this code
#include<algorithm>#include<array>#include<functional>#include<iostream>#include<string_view>intmain(){std::array<int,10>s{5,7,4,2,8,6,1,9,0,3};autoprint=[&s](conststd::string_viewrem){for(autoa:s)std::cout<<a<<' ';std::cout<<": "<<rem<<'\n';};std::sort(s.begin(),s.end());print("sorted with the default operator<");std::sort(s.begin(),s.end(),std::greater<int>());print("sorted with the standard library compare function object");struct{booloperator()(inta,intb)const{returna<b;}}customLess;std::sort(s.begin(),s.end(),customLess);print("sorted with a custom function object");std::sort(s.begin(),s.end(),[](inta,intb){returna>b;});print("sorted with a lambda expression");}Output:
0 1 2 3 4 5 6 7 8 9 : sorted with the default operator< 9 8 7 6 5 4 3 2 1 0 : sorted with the standard library compare function object 0 1 2 3 4 5 6 7 8 9 : sorted with a custom function object 9 8 7 6 5 4 3 2 1 0 : sorted with a lambda expression Defect reports
The following behavior-changing defect reports were applied retroactively to previously published C++ standards.
DR Applied to Behavior as published Correct behavior
C++98 the 𝓞(N·log(N)) time complexity was only required on the average it is required for the worst case See also
(C++20)
sorts a range of elements
(algorithm function object)
sorts the first N elements of a range
(function template & algorithm function object)
(C++20)
sorts a range of elements while preserving relative order between equivalent elements
(function template & algorithm function object)
(C++20)
sorts the elements
(public member function of std::list<T,Allocator>)
sorts the elements
(public member function of std::forward_list<T,Allocator>)
sorts the elements
(public member function of std::hive<T,Allocator>)