template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
I sort(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
safe_iterator_t<Rng>
sort(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Effects: Sorts the elements in the range [first,last).
Returns: last.
Complexity: Ο(Nlog(N)) (where N == last - first) comparisons, and twice as many applications of the projection.
template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
I stable_sort(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
safe_iterator_t<Rng>
stable_sort(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Effects: Sorts the elements in the range [first,last).
Returns: last.
Complexity: Let N == last - first. If enough extra memory is available, N log(N) comparisons. Otherwise, at most N log2(N) comparisons. In either case, twice as many applications of the projection as the number of comparisons.
Remarks: Stable ( ISO/IEC 14882:2014 §[algorithm.stable]).
template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
I partial_sort(I first, I middle, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
safe_iterator_t<Rng>
partial_sort(Rng&& rng, iterator_t<Rng> middle, Comp comp = Comp{},
Proj proj = Proj{});
Returns: last.
Complexity: It takes approximately (last - first) * log(middle - first) comparisons, and exactly twice as many applications of the projection.
template <InputIterator I1, Sentinel<I1> S1, RandomAccessIterator I2, Sentinel<I2> S2,
class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
requires IndirectlyCopyable<I1, I2> && Sortable<I2, Comp, Proj2> &&
IndirectStrictWeakOrder<Comp, projected<I1, Proj1>, projected<I2, Proj2>>
I2
partial_sort_copy(I1 first, S1 last, I2 result_first, S2 result_last,
Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputRange Rng1, RandomAccessRange Rng2, class Comp = less<>,
class Proj1 = identity, class Proj2 = identity>
requires IndirectlyCopyable<iterator_t<Rng1>, iterator_t<Rng2>> &&
Sortable<iterator_t<Rng2>, Comp, Proj2> &&
IndirectStrictWeakOrder<Comp, projected<iterator_t<Rng1>, Proj1>,
projected<iterator_t<Rng2>, Proj2>>
safe_iterator_t<Rng2>
partial_sort_copy(Rng1&& rng, Rng2&& result_rng, Comp comp = Comp{},
Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
Effects: Places the first min(last - first, result_last - result_first) sorted elements into the range [result_first,result_first + min(last - first, result_last - result_first)).
Returns: The smaller of: result_last or result_first + (last - first).
Complexity: Approximately
(last - first) * log(min(last - first, result_last - result_first))
comparisons, and exactly twice as many applications of the projection.
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
bool is_sorted(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <ForwardRange Rng, class Proj = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
bool
is_sorted(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Returns: is_sorted_until(first, last, comp, proj) == last
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
I is_sorted_until(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <ForwardRange Rng, class Proj = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
safe_iterator_t<Rng>
is_sorted_until(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Returns: If distance(first, last) < 2, returns last. Otherwise, returns the last iterator i in [first,last] for which the range [first,i) is sorted.
Complexity: Linear.