11 Algorithms library [algorithms]

11.5 Sorting and related operations [alg.sorting]

11.5.1 Sorting [alg.sort]

11.5.1.1 sort [sort]

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{});

1

Effects: Sorts the elements in the range [first,last).

2

Returns: last.

3

Complexity: Ο(Nlog(N)) (where N == last - first) comparisons, and twice as many applications of the projection.

11.5.1.2 stable_sort [stable.sort]

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{});

1

Effects: Sorts the elements in the range [first,last).

2

Returns: last.

3

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.

4

Remarks: Stable ( ISO/IEC 14882:2014 §[algorithm.stable]).

11.5.1.3 partial_sort [partial.sort]

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{});

1

Effects: Places the first middle - first sorted elements from the range [first,last) into the range [first,middle). The rest of the elements in the range [middle,last) are placed in an unspecified order.

2

Returns: last.

3

Complexity: It takes approximately (last - first) * log(middle - first) comparisons, and exactly twice as many applications of the projection.

11.5.1.4 partial_sort_copy [partial.sort.copy]

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{});

1

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

2

Returns: The smaller of: result_last or result_first + (last - first).

3

Complexity: Approximately 

(last - first) * log(min(last - first, result_last - result_first))

comparisons, and exactly twice as many applications of the projection.

11.5.1.5 is_sorted [is.sorted]

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{});

1

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{});

2

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.

3

Complexity: Linear.