[alg.sorting] - C++14 → C++17

Files changed (1) hide show

tmp/tmpzefr_wpc/{from.md → to.md} +562 -144

tmp/tmpzefr_wpc/{from.md → to.md} RENAMED Viewed

@@ -14,37 +14,43 @@ ordering relation. It is assumed that `comp` will not apply any
 non-constant function through the dereferenced iterator.
 For all algorithms that take `Compare`, there is a version that uses
 `operator<` instead. That is, `comp(*i, *j) != false` defaults to
 `*i < *j != false`. For algorithms other than those described in
-[[alg.binary.search]] to work correctly, `comp` has to induce a strict
-weak ordering on the values.
 The term *strict* refers to the requirement of an irreflexive relation
 (`!comp(x, x)` for all `x`), and the term *weak* to requirements that
 are not as strong as those for a total ordering, but stronger than those
 for a partial ordering. If we define `equiv(a, b)` as
 `!comp(a, b) && !comp(b, a)`, then the requirements are that `comp` and
 `equiv` both be transitive relations:
 - `comp(a, b) && comp(b, c)` implies `comp(a, c)`
-- `equiv(a, b) && equiv(b, c)`
-  implies `equiv(a, c)` Under these conditions, it can be shown that
 - `equiv` is an equivalence relation
 - `comp` induces a well-defined relation on the equivalence classes
   determined by `equiv`
 - The induced relation is a strict total ordering.
 A sequence is *sorted with respect to a comparator* `comp` if for every
 iterator `i` pointing to the sequence and every non-negative integer `n`
 such that `i + n` is a valid iterator pointing to an element of the
 sequence, `comp(*(i + n), *i) == false`.
 A sequence \[`start`, `finish`) is *partitioned with respect to an
 expression* `f(e)` if there exists an integer `n` such that for all
-`0 <= i < distance(start, finish)`, `f(*(start + i))` is true if and
-only if `i < n`.
 In the descriptions of the functions that deal with ordering
 relationships we frequently use a notion of equivalence to describe
 concepts such as stability. The equivalence to which we refer is not
 necessarily an `operator==`, but an equivalence relation induced by the
@@ -56,111 +62,150 @@ equivalent if and only if `!(a < b) && !(b < a)`.
 #### `sort` <a id="sort">[[sort]]</a>
 ``` cpp
 template<class RandomAccessIterator>
   void sort(RandomAccessIterator first, RandomAccessIterator last);
 template<class RandomAccessIterator, class Compare>
   void sort(RandomAccessIterator first, RandomAccessIterator last,
             Compare comp);
 ```
-*Effects:* Sorts the elements in the range \[`first`, `last`).
 *Requires:* `RandomAccessIterator` shall satisfy the requirements of
 `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
 shall satisfy the requirements of `MoveConstructible`
-(Table  [[moveconstructible]]) and of `MoveAssignable`
-(Table  [[moveassignable]]).
-*Complexity:* 𝑂(Nlog(N)) (where N` == last - first`) comparisons.
 #### `stable_sort` <a id="stable.sort">[[stable.sort]]</a>
 ``` cpp
 template<class RandomAccessIterator>
   void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
 template<class RandomAccessIterator, class Compare>
   void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
                    Compare comp);
 ```
-*Effects:* Sorts the elements in the range \[`first`, `last`).
 *Requires:* `RandomAccessIterator` shall satisfy the requirements of
 `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
 shall satisfy the requirements of `MoveConstructible`
-(Table  [[moveconstructible]]) and of `MoveAssignable`
-(Table  [[moveassignable]]).
-*Complexity:* It does at most N log²(N) (where N` == last - first`)
-comparisons; if enough extra memory is available, it is N log(N).
 *Remarks:* Stable ([[algorithm.stable]]).
 #### `partial_sort` <a id="partial.sort">[[partial.sort]]</a>
 ``` cpp
 template<class RandomAccessIterator>
   void partial_sort(RandomAccessIterator first,
                     RandomAccessIterator middle,
                     RandomAccessIterator last);
 template<class RandomAccessIterator, class Compare>
   void partial_sort(RandomAccessIterator first,
                     RandomAccessIterator middle,
                     RandomAccessIterator last,
                     Compare comp);
 ```
 *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.
-*Requires:* `RandomAccessIterator` shall satisfy the requirements of
-`ValueSwappable` ([[swappable.requirements]]). The type of `*first`
-shall satisfy the requirements of `MoveConstructible`
-(Table  [[moveconstructible]]) and of `MoveAssignable`
-(Table  [[moveassignable]]).
-*Complexity:* It takes approximately
-`(last - first) * log(middle - first)` comparisons.
 #### `partial_sort_copy` <a id="partial.sort.copy">[[partial.sort.copy]]</a>
 ``` cpp
 template<class InputIterator, class RandomAccessIterator>
   RandomAccessIterator
     partial_sort_copy(InputIterator first, InputIterator last,
                       RandomAccessIterator result_first,
                       RandomAccessIterator result_last);
 template<class InputIterator, class RandomAccessIterator,
          class Compare>
   RandomAccessIterator
     partial_sort_copy(InputIterator first, InputIterator last,
                       RandomAccessIterator result_first,
                       RandomAccessIterator result_last,
                       Compare comp);
 ```
 *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)`.
-*Requires:* `RandomAccessIterator` shall satisfy the requirements of
-`ValueSwappable` ([[swappable.requirements]]). The type of
-`*result_first` shall satisfy the requirements of `MoveConstructible`
-(Table  [[moveconstructible]]) and of `MoveAssignable`
-(Table  [[moveassignable]]).
 *Complexity:* Approximately
 `(last - first) * log(min(last - first, result_last - result_first))`
 comparisons.
 #### `is_sorted` <a id="is.sorted">[[is.sorted]]</a>
@@ -170,57 +215,97 @@ template<class ForwardIterator>
   bool is_sorted(ForwardIterator first, ForwardIterator last);
 ```
 *Returns:* `is_sorted_until(first, last) == last`
 ``` cpp
 template<class ForwardIterator, class Compare>
   bool is_sorted(ForwardIterator first, ForwardIterator last,
                  Compare comp);
 ```
 *Returns:* `is_sorted_until(first, last, comp) == last`
 ``` cpp
 template<class ForwardIterator>
   ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last);
 template<class ForwardIterator, class Compare>
   ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last,
                                   Compare comp);
 ```
-*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.
 ### Nth element <a id="alg.nth.element">[[alg.nth.element]]</a>
 ``` cpp
 template<class RandomAccessIterator>
   void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                    RandomAccessIterator last);
 template<class RandomAccessIterator, class Compare>
   void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                    RandomAccessIterator last,  Compare comp);
 ```
-After `nth_element` the element in the position pointed to by `nth` is
-the element that would be in that position if the whole range were
-sorted, unless `nth == last`. Also for every iterator `i` in the range
-\[`first`, `nth`) and every iterator `j` in the range \[`nth`, `last`)
-it holds that: `!(*j < *i)` or `comp(*j, *i) == false`.
 *Requires:* `RandomAccessIterator` shall satisfy the requirements of
 `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
 shall satisfy the requirements of `MoveConstructible`
-(Table  [[moveconstructible]]) and of `MoveAssignable`
-(Table  [[moveassignable]]).
-*Complexity:* Linear on average.
 ### Binary search <a id="alg.binary.search">[[alg.binary.search]]</a>
 All of the algorithms in this section are versions of binary search and
 assume that the sequence being searched is partitioned with respect to
@@ -340,77 +425,250 @@ implies `!comp(value, e)`.
 `!(*i < value) && !(value < *i)` or
 `comp(*i, value) == false && comp(value, *i) == false`.
 *Complexity:* At most log₂(`last - first`) + 𝑂(1) comparisons.
 ### Merge <a id="alg.merge">[[alg.merge]]</a>
 ``` cpp
 template<class InputIterator1, class InputIterator2,
          class OutputIterator>
   OutputIterator
     merge(InputIterator1 first1, InputIterator1 last1,
           InputIterator2 first2, InputIterator2 last2,
           OutputIterator result);
 template<class InputIterator1, class InputIterator2,
          class OutputIterator, class Compare>
   OutputIterator
     merge(InputIterator1 first1, InputIterator1 last1,
           InputIterator2 first2, InputIterator2 last2,
           OutputIterator result, Compare comp);
 ```
 *Effects:*  Copies all the elements of the two ranges \[`first1`,
 `last1`) and \[`first2`, `last2`) into the range \[`result`,
 `result_last`), where `result_last` is
 `result + (last1 - first1) + (last2 - first2)`, such that the resulting
 range satisfies `is_sorted(result, result_last)` or
 `is_sorted(result, result_last, comp)`, respectively.
-*Requires:* The ranges \[`first1`, `last1`) and \[`first2`, `last2`)
-shall be sorted with respect to `operator<` or `comp`. The resulting
-range shall not overlap with either of the original ranges.
 *Returns:* `result + (last1 - first1) + (last2 - first2)`.
-*Complexity:* At most `(last1 - first1) + (last2 - first2) - 1`
   comparisons.
 *Remarks:* Stable ([[algorithm.stable]]).
 ``` cpp
 template<class BidirectionalIterator>
   void inplace_merge(BidirectionalIterator first,
                      BidirectionalIterator middle,
                      BidirectionalIterator last);
 template<class BidirectionalIterator, class Compare>
   void inplace_merge(BidirectionalIterator first,
                      BidirectionalIterator middle,
                      BidirectionalIterator last, Compare comp);
 ```
 *Effects:* Merges two sorted consecutive ranges \[`first`, `middle`) and
 \[`middle`, `last`), putting the result of the merge into the range
 \[`first`, `last`). The resulting range will be in non-decreasing order;
 that is, for every iterator `i` in \[`first`, `last`) other than
 `first`, the condition `*i < *(i - 1)` or, respectively,
-`comp(*i, *(i - 1))` will be false.
-*Requires:* The ranges \[`first`, `middle`) and \[`middle`, `last`)
-shall be sorted with respect to `operator<` or `comp`.
-`BidirectionalIterator` shall satisfy the requirements of
-`ValueSwappable` ([[swappable.requirements]]). The type of `*first`
-shall satisfy the requirements of `MoveConstructible`
-(Table  [[moveconstructible]]) and of `MoveAssignable`
-(Table  [[moveassignable]]).
-*Complexity:* When enough additional memory is available,
-`(last - first) - 1` comparisons. If no additional memory is available,
-an algorithm with complexity N log(N) (where `N` is equal to
-`last - first`) may be used.
 *Remarks:* Stable ([[algorithm.stable]]).
 ### Set operations on sorted structures <a id="alg.set.operations">[[alg.set.operations]]</a>
@@ -425,15 +683,24 @@ to contain the maximum number of occurrences of every element,
 ``` cpp
 template<class InputIterator1, class InputIterator2>
   bool includes(InputIterator1 first1, InputIterator1 last1,
                 InputIterator2 first2, InputIterator2 last2);
 template<class InputIterator1, class InputIterator2, class Compare>
   bool includes(InputIterator1 first1, InputIterator1 last1,
                 InputIterator2 first2, InputIterator2 last2,
                 Compare comp);
 ```
 *Returns:* `true` if \[`first2`, `last2`) is empty or if every element
 in the range \[`first2`, `last2`) is contained in the range \[`first1`,
 `last1`). Returns `false` otherwise.
@@ -448,26 +715,40 @@ template<class InputIterator1, class InputIterator2,
          class OutputIterator>
   OutputIterator
     set_union(InputIterator1 first1, InputIterator1 last1,
               InputIterator2 first2, InputIterator2 last2,
               OutputIterator result);
 template<class InputIterator1, class InputIterator2,
          class OutputIterator, class Compare>
   OutputIterator
     set_union(InputIterator1 first1, InputIterator1 last1,
               InputIterator2 first2, InputIterator2 last2,
               OutputIterator result, Compare comp);
 ```
 *Effects:* Constructs a sorted union of the elements from the two
 ranges; that is, the set of elements that are present in one or both of
 the ranges.
-*Requires:* The resulting range shall not overlap with either of the
-original ranges.
 *Returns:* The end of the constructed range.
 *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
 comparisons.
@@ -485,26 +766,40 @@ template<class InputIterator1, class InputIterator2,
          class OutputIterator>
   OutputIterator
     set_intersection(InputIterator1 first1, InputIterator1 last1,
                      InputIterator2 first2, InputIterator2 last2,
                      OutputIterator result);
 template<class InputIterator1, class InputIterator2,
          class OutputIterator, class Compare>
   OutputIterator
     set_intersection(InputIterator1 first1, InputIterator1 last1,
                      InputIterator2 first2, InputIterator2 last2,
                      OutputIterator result, Compare comp);
 ```
 *Effects:* Constructs a sorted intersection of the elements from the two
 ranges; that is, the set of elements that are present in both of the
 ranges.
-*Requires:* The resulting range shall not overlap with either of the
-original ranges.
 *Returns:* The end of the constructed range.
 *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
 comparisons.
@@ -520,26 +815,40 @@ template<class InputIterator1, class InputIterator2,
          class OutputIterator>
   OutputIterator
     set_difference(InputIterator1 first1, InputIterator1 last1,
                    InputIterator2 first2, InputIterator2 last2,
                    OutputIterator result);
 template<class InputIterator1, class InputIterator2,
          class OutputIterator, class Compare>
   OutputIterator
     set_difference(InputIterator1 first1, InputIterator1 last1,
                    InputIterator2 first2, InputIterator2 last2,
                    OutputIterator result, Compare comp);
 ```
 *Effects:* Copies the elements of the range \[`first1`, `last1`) which
 are not present in the range \[`first2`, `last2`) to the range beginning
 at `result`. The elements in the constructed range are sorted.
-*Requires:* The resulting range shall not overlap with either of the
-original ranges.
 *Returns:* The end of the constructed range.
 *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
 comparisons.
@@ -555,28 +864,42 @@ template<class InputIterator1, class InputIterator2,
          class OutputIterator>
   OutputIterator
     set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
                              InputIterator2 first2, InputIterator2 last2,
                              OutputIterator result);
 template<class InputIterator1, class InputIterator2,
          class OutputIterator, class Compare>
   OutputIterator
     set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
                              InputIterator2 first2, InputIterator2 last2,
                              OutputIterator result, Compare comp);
 ```
 *Effects:* Copies the elements of the range \[`first1`, `last1`) that
 are not present in the range \[`first2`, `last2`), and the elements of
 the range \[`first2`, `last2`) that are not present in the range
 \[`first1`, `last1`) to the range beginning at `result`. The elements in
 the constructed range are sorted.
-*Requires:* The resulting range shall not overlap with either of the
-original ranges.
 *Returns:* The end of the constructed range.
 *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
 comparisons.
@@ -588,24 +911,17 @@ copied to the output range: the last m - n of these elements from
 \[`first2`, `last2`) if m < n.
 ### Heap operations <a id="alg.heap.operations">[[alg.heap.operations]]</a>
 A *heap* is a particular organization of elements in a range between two
-random access iterators \[`a`, `b`). Its two key properties are:
-- **(1)} There is no element greater than
-\texttt{\*a}
-in the range and**
-- **`(2)} \texttt{*a}
-may be removed by
-\texttt{pop_heap()},
-or a new element added by
-\texttt{push_heap()},
-in
-$\mathcal{O}(\log(N))$
-time.`**
 These properties make heaps useful as priority queues.
 `make_heap()`
@@ -621,19 +937,19 @@ template<class RandomAccessIterator>
 template<class RandomAccessIterator, class Compare>
   void push_heap(RandomAccessIterator first, RandomAccessIterator last,
                  Compare comp);
 ```
-*Effects:* Places the value in the location `last - 1` into the
-resulting heap \[`first`, `last`).
 *Requires:* The range \[`first`, `last - 1`) shall be a valid heap. The
 type of `*first` shall satisfy the `MoveConstructible` requirements
-(Table  [[moveconstructible]]) and the `MoveAssignable` requirements
-(Table  [[moveassignable]]).
-*Complexity:* At most `log(last - first)` comparisons.
 #### `pop_heap` <a id="pop.heap">[[pop.heap]]</a>
 ``` cpp
 template<class RandomAccessIterator>
@@ -646,17 +962,17 @@ template<class RandomAccessIterator, class Compare>
 *Requires:* The range \[`first`, `last`) shall be a valid non-empty
 heap. `RandomAccessIterator` shall satisfy the requirements of
 `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
 shall satisfy the requirements of `MoveConstructible`
-(Table  [[moveconstructible]]) and of `MoveAssignable`
-(Table  [[moveassignable]]).
 *Effects:* Swaps the value in the location `first` with the value in the
 location `last - 1` and makes \[`first`, `last - 1`) into a heap.
-*Complexity:* At most `2 * log(last - first)` comparisons.
 #### `make_heap` <a id="make.heap">[[make.heap]]</a>
 ``` cpp
 template<class RandomAccessIterator>
@@ -665,17 +981,17 @@ template<class RandomAccessIterator>
 template<class RandomAccessIterator, class Compare>
   void make_heap(RandomAccessIterator first, RandomAccessIterator last,
                  Compare comp);
 ```
-*Effects:* Constructs a heap out of the range \[`first`, `last`).
 *Requires:* The type of `*first` shall satisfy the `MoveConstructible`
-requirements (Table  [[moveconstructible]]) and the `MoveAssignable`
-requirements (Table  [[moveassignable]]).
-*Complexity:* At most `3 * (last - first)` comparisons.
 #### `sort_heap` <a id="sort.heap">[[sort.heap]]</a>
 ``` cpp
 template<class RandomAccessIterator>
@@ -684,47 +1000,76 @@ template<class RandomAccessIterator>
 template<class RandomAccessIterator, class Compare>
   void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
                  Compare comp);
 ```
-*Effects:* Sorts elements in the heap \[`first`, `last`).
 *Requires:* The range \[`first`, `last`) shall be a valid heap.
 `RandomAccessIterator` shall satisfy the requirements of
 `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
 shall satisfy the requirements of `MoveConstructible`
-(Table  [[moveconstructible]]) and of `MoveAssignable`
-(Table  [[moveassignable]]).
-*Complexity:* At most N log(N) comparisons (where `N == last - first`).
 #### `is_heap` <a id="is.heap">[[is.heap]]</a>
 ``` cpp
 template<class RandomAccessIterator>
   bool is_heap(RandomAccessIterator first, RandomAccessIterator last);
 ```
 *Returns:* `is_heap_until(first, last) == last`
 ``` cpp
 template<class RandomAccessIterator, class Compare>
   bool is_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
 ```
 *Returns:* `is_heap_until(first, last, comp) == last`
 ``` cpp
 template<class RandomAccessIterator>
   RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last);
 template<class RandomAccessIterator, class Compare>
   RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last,
                                      Compare comp);
 ```
-*Returns:* If `distance(first, last) < 2`, returns `last`. Otherwise,
-returns the last iterator `i` in \[`first`, `last`\] for which the range
 \[`first`, `i`) is a heap.
 *Complexity:* Linear.
 ### Minimum and maximum <a id="alg.min.max">[[alg.min.max]]</a>
@@ -733,68 +1078,76 @@ returns the last iterator `i` in \[`first`, `last`\] for which the range
 template<class T> constexpr const T& min(const T& a, const T& b);
 template<class T, class Compare>
   constexpr const T& min(const T& a, const T& b, Compare comp);
 ```
-*Requires:* Type `T` is `LessThanComparable`
-(Table  [[lessthancomparable]]).
 *Returns:* The smaller value.
 *Remarks:* Returns the first argument when the arguments are equivalent.
 ``` cpp
 template<class T>
   constexpr T min(initializer_list<T> t);
 template<class T, class Compare>
   constexpr T min(initializer_list<T> t, Compare comp);
 ```
-*Requires:* `T` is `LessThanComparable` and `CopyConstructible` and
-`t.size() > 0`.
 *Returns:* The smallest value in the initializer_list.
 *Remarks:* Returns a copy of the leftmost argument when several
 arguments are equivalent to the smallest.
 ``` cpp
 template<class T> constexpr const T& max(const T& a, const T& b);
 template<class T, class Compare>
   constexpr const T& max(const T& a, const T& b, Compare comp);
 ```
-*Requires:* Type `T` is `LessThanComparable`
-(Table  [[lessthancomparable]]).
 *Returns:* The larger value.
 *Remarks:* Returns the first argument when the arguments are equivalent.
 ``` cpp
 template<class T>
   constexpr T max(initializer_list<T> t);
 template<class T, class Compare>
   constexpr T max(initializer_list<T> t, Compare comp);
 ```
-*Requires:* `T` is `LessThanComparable` and `CopyConstructible` and
-`t.size() > 0`.
 *Returns:* The largest value in the initializer_list.
 *Remarks:* Returns a copy of the leftmost argument when several
 arguments are equivalent to the largest.
 ``` cpp
 template<class T> constexpr pair<const T&, const T&> minmax(const T& a, const T& b);
 template<class T, class Compare>
   constexpr pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp);
 ```
-*Requires:* Type `T` shall be `LessThanComparable`
-(Table  [[lessthancomparable]]).
 *Returns:* `pair<const T&, const T&>(b, a)` if `b` is smaller than `a`,
 and `pair<const T&, const T&>(a, b)` otherwise.
 *Remarks:* Returns `pair<const T&, const T&>(a, b)` when the arguments
@@ -807,116 +1160,179 @@ template<class T>
   constexpr pair<T, T> minmax(initializer_list<T> t);
 template<class T, class Compare>
   constexpr pair<T, T> minmax(initializer_list<T> t, Compare comp);
 ```
-*Requires:* `T` is `LessThanComparable` and `CopyConstructible` and
-`t.size() > 0`.
 *Returns:* `pair<T, T>(x, y)`, where `x` has the smallest and `y` has
 the largest value in the initializer list.
 *Remarks:* `x` is a copy of the leftmost argument when several arguments
 are equivalent to the smallest. `y` is a copy of the rightmost argument
 when several arguments are equivalent to the largest.
-*Complexity:* At most `(3/2) * t.size()` applications of the
-corresponding predicate.
 ``` cpp
 template<class ForwardIterator>
-  ForwardIterator min_element(ForwardIterator first, ForwardIterator last);
 template<class ForwardIterator, class Compare>
-  ForwardIterator min_element(ForwardIterator first, ForwardIterator last,
                               Compare comp);
 ```
 *Returns:* The first iterator `i` in the range \[`first`, `last`) such
 that for every iterator `j` in the range \[`first`, `last`) the
 following corresponding conditions hold: `!(*j < *i)` or
 `comp(*j, *i) == false`. Returns `last` if `first == last`.
-*Complexity:* Exactly `max((last - first) - 1, 0)` applications of the
 corresponding comparisons.
 ``` cpp
 template<class ForwardIterator>
-  ForwardIterator max_element(ForwardIterator first, ForwardIterator last);
 template<class ForwardIterator, class Compare>
-  ForwardIterator max_element(ForwardIterator first, ForwardIterator last,
                               Compare comp);
 ```
 *Returns:* The first iterator `i` in the range \[`first`, `last`) such
 that for every iterator `j` in the range \[`first`, `last`) the
 following corresponding conditions hold: `!(*i < *j)` or
 `comp(*i, *j) == false`. Returns `last` if `first == last`.
-*Complexity:* Exactly `max((last - first) - 1, 0)` applications of the
 corresponding comparisons.
 ``` cpp
 template<class ForwardIterator>
-  pair<ForwardIterator, ForwardIterator>
     minmax_element(ForwardIterator first, ForwardIterator last);
-template<class ForwardIterator, class Compare>
   pair<ForwardIterator, ForwardIterator>
     minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
 ```
 *Returns:* `make_pair(first, first)` if \[`first`, `last`) is empty,
 otherwise `make_pair(m, M)`, where `m` is the first iterator in
 \[`first`, `last`) such that no iterator in the range refers to a
-smaller element, and where `M` is the last iterator in \[`first`,
 `last`) such that no iterator in the range refers to a larger element.
-*Complexity:* At most $max(\lfloor{\frac{3}{2}} (N-1)\rfloor, 0)$
-applications of the corresponding predicate, where N is
-`distance(first, last)`.
 ### Lexicographical comparison <a id="alg.lex.comparison">[[alg.lex.comparison]]</a>
 ``` cpp
 template<class InputIterator1, class InputIterator2>
   bool
     lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
                             InputIterator2 first2, InputIterator2 last2);
 template<class InputIterator1, class InputIterator2, class Compare>
   bool
     lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
                             InputIterator2 first2, InputIterator2 last2,
                             Compare comp);
 ```
 *Returns:* `true` if the sequence of elements defined by the range
 \[`first1`, `last1`) is lexicographically less than the sequence of
 elements defined by the range \[`first2`, `last2`) and `false`
 otherwise.
-*Complexity:* At most `2*min((last1 - first1), (last2 - first2))`
 applications of the corresponding comparison.
 *Remarks:* If two sequences have the same number of elements and their
-corresponding elements are equivalent, then neither sequence is
 lexicographically less than the other. If one sequence is a prefix of
 the other, then the shorter sequence is lexicographically less than the
 longer sequence. Otherwise, the lexicographical comparison of the
 sequences yields the same result as the comparison of the first
 corresponding pair of elements that are not equivalent.
 ``` cpp
-for ( ; first1 != last1 && first2 != last2 ; ++first1, ++first2) {
   if (*first1 < *first2) return true;
   if (*first2 < *first1) return false;
 }
 return first1 == last1 && first2 != last2;
 ```
-*Remarks:*  An empty sequence is lexicographically less than any
-non-empty sequence, but not less than any empty sequence.
 ### Permutation generators <a id="alg.permutation.generators">[[alg.permutation.generators]]</a>
 ``` cpp
 template<class BidirectionalIterator>
@@ -926,19 +1342,21 @@ template<class BidirectionalIterator>
 template<class BidirectionalIterator, class Compare>
   bool next_permutation(BidirectionalIterator first,
                         BidirectionalIterator last, Compare comp);
 ```
 *Effects:* Takes a sequence defined by the range \[`first`, `last`) and
 transforms it into the next permutation. The next permutation is found
 by assuming that the set of all permutations is lexicographically sorted
-with respect to `operator<` or `comp`. If such a permutation exists, it
-returns `true`. Otherwise, it transforms the sequence into the smallest
-permutation, that is, the ascendingly sorted one, and returns `false`.
-*Requires:* `BidirectionalIterator` shall satisfy the requirements of
-`ValueSwappable` ([[swappable.requirements]]).
 *Complexity:* At most `(last - first) / 2` swaps.
 ``` cpp
 template<class BidirectionalIterator>
@@ -948,19 +1366,19 @@ template<class BidirectionalIterator>
 template<class BidirectionalIterator, class Compare>
   bool prev_permutation(BidirectionalIterator first,
                         BidirectionalIterator last, Compare comp);
 ```
 *Effects:* Takes a sequence defined by the range \[`first`, `last`) and
 transforms it into the previous permutation. The previous permutation is
 found by assuming that the set of all permutations is lexicographically
 sorted with respect to `operator<` or `comp`.
 *Returns:* `true` if such a permutation exists. Otherwise, it transforms
 the sequence into the largest permutation, that is, the descendingly
 sorted one, and returns `false`.
-*Requires:* `BidirectionalIterator` shall satisfy the requirements of
-`ValueSwappable` ([[swappable.requirements]]).
 *Complexity:* At most `(last - first) / 2` swaps.

 non-constant function through the dereferenced iterator.
 For all algorithms that take `Compare`, there is a version that uses
 `operator<` instead. That is, `comp(*i, *j) != false` defaults to
 `*i < *j != false`. For algorithms other than those described in
+[[alg.binary.search]], `comp` shall induce a strict weak ordering on the
+values.
 The term *strict* refers to the requirement of an irreflexive relation
 (`!comp(x, x)` for all `x`), and the term *weak* to requirements that
 are not as strong as those for a total ordering, but stronger than those
 for a partial ordering. If we define `equiv(a, b)` as
 `!comp(a, b) && !comp(b, a)`, then the requirements are that `comp` and
 `equiv` both be transitive relations:
 - `comp(a, b) && comp(b, c)` implies `comp(a, c)`
+- `equiv(a, b) && equiv(b, c)` implies `equiv(a, c)`
+[*Note 1*:
+Under these conditions, it can be shown that
 - `equiv` is an equivalence relation
 - `comp` induces a well-defined relation on the equivalence classes
   determined by `equiv`
 - The induced relation is a strict total ordering.
+— *end note*]
 A sequence is *sorted with respect to a comparator* `comp` if for every
 iterator `i` pointing to the sequence and every non-negative integer `n`
 such that `i + n` is a valid iterator pointing to an element of the
 sequence, `comp(*(i + n), *i) == false`.
 A sequence \[`start`, `finish`) is *partitioned with respect to an
 expression* `f(e)` if there exists an integer `n` such that for all
+`0 <= i < (finish - start)`, `f(*(start + i))` is `true` if and only if
+`i < n`.
 In the descriptions of the functions that deal with ordering
 relationships we frequently use a notion of equivalence to describe
 concepts such as stability. The equivalence to which we refer is not
 necessarily an `operator==`, but an equivalence relation induced by the
 #### `sort` <a id="sort">[[sort]]</a>
 ``` cpp
 template<class RandomAccessIterator>
   void sort(RandomAccessIterator first, RandomAccessIterator last);
+template<class ExecutionPolicy, class RandomAccessIterator>
+  void sort(ExecutionPolicy&& exec,
+            RandomAccessIterator first, RandomAccessIterator last);
 template<class RandomAccessIterator, class Compare>
   void sort(RandomAccessIterator first, RandomAccessIterator last,
             Compare comp);
+template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
+  void sort(ExecutionPolicy&& exec,
+            RandomAccessIterator first, RandomAccessIterator last,
+            Compare comp);
 ```
 *Requires:* `RandomAccessIterator` shall satisfy the requirements of
 `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
 shall satisfy the requirements of `MoveConstructible`
+(Table  [[tab:moveconstructible]]) and of `MoveAssignable`
+(Table  [[tab:moveassignable]]).
+*Effects:* Sorts the elements in the range \[`first`, `last`).
+*Complexity:* 𝑂(N log N) comparisons, where N = `last - first`.
 #### `stable_sort` <a id="stable.sort">[[stable.sort]]</a>
 ``` cpp
 template<class RandomAccessIterator>
   void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
+template<class ExecutionPolicy, class RandomAccessIterator>
+  void stable_sort(ExecutionPolicy&& exec,
+                   RandomAccessIterator first, RandomAccessIterator last);
 template<class RandomAccessIterator, class Compare>
   void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
                    Compare comp);
+template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
+  void stable_sort(ExecutionPolicy&& exec,
+                   RandomAccessIterator first, RandomAccessIterator last,
+                   Compare comp);
 ```
 *Requires:* `RandomAccessIterator` shall satisfy the requirements of
 `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
 shall satisfy the requirements of `MoveConstructible`
+(Table  [[tab:moveconstructible]]) and of `MoveAssignable`
+(Table  [[tab:moveassignable]]).
+*Effects:* Sorts the elements in the range \[`first`, `last`).
+*Complexity:* At most N log²(N) comparisons, where N = `last - first`,
+but only N log N comparisons if there is enough extra memory.
 *Remarks:* Stable ([[algorithm.stable]]).
 #### `partial_sort` <a id="partial.sort">[[partial.sort]]</a>
 ``` cpp
 template<class RandomAccessIterator>
   void partial_sort(RandomAccessIterator first,
                     RandomAccessIterator middle,
                     RandomAccessIterator last);
+template<class ExecutionPolicy, class RandomAccessIterator>
+  void partial_sort(ExecutionPolicy&& exec,
+                    RandomAccessIterator first,
+                    RandomAccessIterator middle,
+                    RandomAccessIterator last);
 template<class RandomAccessIterator, class Compare>
   void partial_sort(RandomAccessIterator first,
                     RandomAccessIterator middle,
                     RandomAccessIterator last,
                     Compare comp);
+template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
+  void partial_sort(ExecutionPolicy&& exec,
+                    RandomAccessIterator first,
+                    RandomAccessIterator middle,
+                    RandomAccessIterator last,
+                    Compare comp);
 ```
+*Requires:* `RandomAccessIterator` shall satisfy the requirements of
+`ValueSwappable` ([[swappable.requirements]]). The type of `*first`
+shall satisfy the requirements of `MoveConstructible`
+(Table  [[tab:moveconstructible]]) and of `MoveAssignable`
+(Table  [[tab:moveassignable]]).
 *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.
+*Complexity:* Approximately `(last - first) * log(middle - first)`
+comparisons.
 #### `partial_sort_copy` <a id="partial.sort.copy">[[partial.sort.copy]]</a>
 ``` cpp
 template<class InputIterator, class RandomAccessIterator>
   RandomAccessIterator
     partial_sort_copy(InputIterator first, InputIterator last,
                       RandomAccessIterator result_first,
                       RandomAccessIterator result_last);
+template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator>
+  RandomAccessIterator
+    partial_sort_copy(ExecutionPolicy&& exec,
+                      ForwardIterator first, ForwardIterator last,
+                      RandomAccessIterator result_first,
+                      RandomAccessIterator result_last);
 template<class InputIterator, class RandomAccessIterator,
          class Compare>
   RandomAccessIterator
     partial_sort_copy(InputIterator first, InputIterator last,
                       RandomAccessIterator result_first,
                       RandomAccessIterator result_last,
                       Compare comp);
+template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator,
+         class Compare>
+  RandomAccessIterator
+    partial_sort_copy(ExecutionPolicy&& exec,
+                      ForwardIterator first, ForwardIterator last,
+                      RandomAccessIterator result_first,
+                      RandomAccessIterator result_last,
+                      Compare comp);
 ```
+*Requires:* `RandomAccessIterator` shall satisfy the requirements of
+`ValueSwappable` ([[swappable.requirements]]). The type of
+`*result_first` shall satisfy the requirements of `MoveConstructible`
+(Table  [[tab:moveconstructible]]) and of `MoveAssignable`
+(Table  [[tab:moveassignable]]).
 *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.
 #### `is_sorted` <a id="is.sorted">[[is.sorted]]</a>
   bool is_sorted(ForwardIterator first, ForwardIterator last);
 ```
 *Returns:* `is_sorted_until(first, last) == last`
+``` cpp
+template<class ExecutionPolicy, class ForwardIterator>
+  bool is_sorted(ExecutionPolicy&& exec,
+                 ForwardIterator first, ForwardIterator last);
+```
+*Returns:*
+`is_sorted_until(std::forward<ExecutionPolicy>(exec), first, last) == last`
 ``` cpp
 template<class ForwardIterator, class Compare>
   bool is_sorted(ForwardIterator first, ForwardIterator last,
                  Compare comp);
 ```
 *Returns:* `is_sorted_until(first, last, comp) == last`
+``` cpp
+template<class ExecutionPolicy, class ForwardIterator, class Compare>
+  bool is_sorted(ExecutionPolicy&& exec,
+                 ForwardIterator first, ForwardIterator last,
+                 Compare comp);
+```
+*Returns:*
+``` cpp
+is_sorted_until(std::forward<ExecutionPolicy>(exec), first, last, comp) == last
+```
 ``` cpp
 template<class ForwardIterator>
   ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last);
+template<class ExecutionPolicy, class ForwardIterator>
+  ForwardIterator is_sorted_until(ExecutionPolicy&& exec,
+                                  ForwardIterator first, ForwardIterator last);
 template<class ForwardIterator, class Compare>
   ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last,
                                   Compare comp);
+template<class ExecutionPolicy, class ForwardIterator, class Compare>
+  ForwardIterator is_sorted_until(ExecutionPolicy&& exec,
+                                  ForwardIterator first, ForwardIterator last,
+                                  Compare comp);
 ```
+*Returns:* If `(last - first) < 2`, returns `last`. Otherwise, returns
+the last iterator `i` in \[`first`, `last`\] for which the range
 \[`first`, `i`) is sorted.
 *Complexity:* Linear.
 ### Nth element <a id="alg.nth.element">[[alg.nth.element]]</a>
 ``` cpp
 template<class RandomAccessIterator>
   void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                    RandomAccessIterator last);
+template<class ExecutionPolicy, class RandomAccessIterator>
+  void nth_element(ExecutionPolicy&& exec,
+                   RandomAccessIterator first, RandomAccessIterator nth,
+                   RandomAccessIterator last);
 template<class RandomAccessIterator, class Compare>
   void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                    RandomAccessIterator last,  Compare comp);
+template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
+  void nth_element(ExecutionPolicy&& exec,
+                   RandomAccessIterator first, RandomAccessIterator nth,
+                   RandomAccessIterator last, Compare comp);
 ```
 *Requires:* `RandomAccessIterator` shall satisfy the requirements of
 `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
 shall satisfy the requirements of `MoveConstructible`
+(Table  [[tab:moveconstructible]]) and of `MoveAssignable`
+(Table  [[tab:moveassignable]]).
+*Effects:* After `nth_element` the element in the position pointed to by
+`nth` is the element that would be in that position if the whole range
+were sorted, unless `nth == last`. Also for every iterator `i` in the
+range \[`first`, `nth`) and every iterator `j` in the range \[`nth`,
+`last`) it holds that: `!(*j < *i)` or `comp(*j, *i) == false`.
+*Complexity:* For the overloads with no `ExecutionPolicy`, linear on
+average. For the overloads with an `ExecutionPolicy`, 𝑂(N) applications
+of the predicate, and 𝑂(N log N) swaps, where N = `last - first`.
 ### Binary search <a id="alg.binary.search">[[alg.binary.search]]</a>
 All of the algorithms in this section are versions of binary search and
 assume that the sequence being searched is partitioned with respect to
 `!(*i < value) && !(value < *i)` or
 `comp(*i, value) == false && comp(value, *i) == false`.
 *Complexity:* At most log₂(`last - first`) + 𝑂(1) comparisons.
+### Partitions <a id="alg.partitions">[[alg.partitions]]</a>
+``` cpp
+template <class InputIterator, class Predicate>
+  bool is_partitioned(InputIterator first, InputIterator last, Predicate pred);
+template <class ExecutionPolicy, class ForwardIterator, class Predicate>
+  bool is_partitioned(ExecutionPolicy&& exec,
+                      ForwardIterator first, ForwardIterator last, Predicate pred);
+```
+*Requires:* For the overload with no `ExecutionPolicy`,
+`InputIterator`’s value type shall be convertible to `Predicate`’s
+argument type. For the overload with an `ExecutionPolicy`,
+`ForwardIterator`’s value type shall be convertible to `Predicate`’s
+argument type.
+*Returns:* `true` if \[`first`, `last`) is empty or if \[`first`,
+`last`) is partitioned by `pred`, i.e. if all elements that satisfy
+`pred` appear before those that do not.
+*Complexity:* Linear. At most `last - first` applications of `pred`.
+``` cpp
+template<class ForwardIterator, class Predicate>
+  ForwardIterator
+    partition(ForwardIterator first, ForwardIterator last, Predicate pred);
+template<class ExecutionPolicy, class ForwardIterator, class Predicate>
+  ForwardIterator
+    partition(ExecutionPolicy&& exec,
+              ForwardIterator first, ForwardIterator last, Predicate pred);
+```
+*Requires:* `ForwardIterator` shall satisfy the requirements of
+`ValueSwappable` ([[swappable.requirements]]).
+*Effects:* Places all the elements in the range \[`first`, `last`) that
+satisfy `pred` before all the elements that do not satisfy it.
+*Returns:* An iterator `i` such that for every iterator `j` in the range
+\[`first`, `i`) `pred(*j) != false`, and for every iterator `k` in the
+range \[`i`, `last`), `pred(*k) == false`.
+*Complexity:* Let N = `last - first`:
+- For the overload with no `ExecutionPolicy`, exactly N applications of
+  the predicate. At most N / 2 swaps if `ForwardIterator` meets the
+  `BidirectionalIterator` requirements and at most N swaps otherwise.
+- For the overload with an `ExecutionPolicy`, 𝑂(N log N) swaps and 𝑂(N)
+  applications of the predicate.
+``` cpp
+template<class BidirectionalIterator, class Predicate>
+  BidirectionalIterator
+    stable_partition(BidirectionalIterator first, BidirectionalIterator last,
+                     Predicate pred);
+template<class ExecutionPolicy, class BidirectionalIterator, class Predicate>
+  BidirectionalIterator
+    stable_partition(ExecutionPolicy&& exec,
+                     BidirectionalIterator first, BidirectionalIterator last,
+                     Predicate pred);
+```
+*Requires:* `BidirectionalIterator` shall satisfy the requirements of
+`ValueSwappable` ([[swappable.requirements]]). The type of `*first`
+shall satisfy the requirements of `MoveConstructible`
+(Table  [[tab:moveconstructible]]) and of `MoveAssignable`
+(Table  [[tab:moveassignable]]).
+*Effects:* Places all the elements in the range \[`first`, `last`) that
+satisfy `pred` before all the elements that do not satisfy it.
+*Returns:* An iterator `i` such that for every iterator `j` in the range
+\[`first`, `i`), `pred(*j) != false`, and for every iterator `k` in the
+range \[`i`, `last`), `pred(*k) == false`. The relative order of the
+elements in both groups is preserved.
+*Complexity:* Let N = `last - first`:
+- For the overload with no `ExecutionPolicy`, at most N log N swaps, but
+  only 𝑂(N) swaps if there is enough extra memory. Exactly N
+  applications of the predicate.
+- For the overload with an `ExecutionPolicy`, 𝑂(N log N) swaps and 𝑂(N)
+  applications of the predicate.
+``` cpp
+template <class InputIterator, class OutputIterator1,
+          class OutputIterator2, class Predicate>
+  pair<OutputIterator1, OutputIterator2>
+    partition_copy(InputIterator first, InputIterator last,
+                   OutputIterator1 out_true, OutputIterator2 out_false,
+                   Predicate pred);
+template <class ExecutionPolicy, class ForwardIterator, class ForwardIterator1,
+          class ForwardIterator2, class Predicate>
+  pair<ForwardIterator1, ForwardIterator2>
+    partition_copy(ExecutionPolicy&& exec,
+                   ForwardIterator first, ForwardIterator last,
+                   ForwardIterator1 out_true, ForwardIterator2 out_false,
+                   Predicate pred);
+```
+*Requires:*
+- For the overload with no `ExecutionPolicy`, `InputIterator`’s value
+  type shall be `CopyAssignable` (Table  [[tab:copyassignable]]), and
+  shall be writable ([[iterator.requirements.general]]) to the
+  `out_true` and `out_false` `OutputIterator`s, and shall be convertible
+  to `Predicate`’s argument type.
+- For the overload with an `ExecutionPolicy`, `ForwardIterator`’s value
+  type shall be `CopyAssignable`, and shall be writable to the
+  `out_true` and `out_false` `ForwardIterator`s, and shall be
+  convertible to `Predicate`’s argument type. \[*Note 1*: There may be a
+  performance cost if `ForwardIterator`’s value type is not
+  `CopyConstructible`. — *end note*]
+- For both overloads, the input range shall not overlap with either of
+  the output ranges.
+*Effects:* For each iterator `i` in \[`first`, `last`), copies `*i` to
+the output range beginning with `out_true` if `pred(*i)` is `true`, or
+to the output range beginning with `out_false` otherwise.
+*Returns:* A pair `p` such that `p.first` is the end of the output range
+beginning at `out_true` and `p.second` is the end of the output range
+beginning at `out_false`.
+*Complexity:* Exactly `last - first` applications of `pred`.
+``` cpp
+template<class ForwardIterator, class Predicate>
+  ForwardIterator partition_point(ForwardIterator first,
+                                  ForwardIterator last,
+                                  Predicate pred);
+```
+*Requires:* `ForwardIterator`’s value type shall be convertible to
+`Predicate`’s argument type. \[`first`, `last`) shall be partitioned by
+`pred`, i.e. all elements that satisfy `pred` shall appear before those
+that do not.
+*Returns:* An iterator `mid` such that `all_of(first, mid, pred)` and
+`none_of(mid, last, pred)` are both `true`.
+*Complexity:* 𝑂(log(`last - first`)) applications of `pred`.
 ### Merge <a id="alg.merge">[[alg.merge]]</a>
 ``` cpp
 template<class InputIterator1, class InputIterator2,
          class OutputIterator>
   OutputIterator
     merge(InputIterator1 first1, InputIterator1 last1,
           InputIterator2 first2, InputIterator2 last2,
           OutputIterator result);
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
+         class ForwardIterator>
+  ForwardIterator
+    merge(ExecutionPolicy&& exec,
+          ForwardIterator1 first1, ForwardIterator1 last1,
+          ForwardIterator2 first2, ForwardIterator2 last2,
+          ForwardIterator result);
 template<class InputIterator1, class InputIterator2,
          class OutputIterator, class Compare>
   OutputIterator
     merge(InputIterator1 first1, InputIterator1 last1,
           InputIterator2 first2, InputIterator2 last2,
           OutputIterator result, Compare comp);
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
+         class ForwardIterator, class Compare>
+  ForwardIterator
+    merge(ExecutionPolicy&& exec,
+          ForwardIterator1 first1, ForwardIterator1 last1,
+          ForwardIterator2 first2, ForwardIterator2 last2,
+          ForwardIterator result, Compare comp);
 ```
+*Requires:* The ranges \[`first1`, `last1`) and \[`first2`, `last2`)
+shall be sorted with respect to `operator<` or `comp`. The resulting
+range shall not overlap with either of the original ranges.
 *Effects:*  Copies all the elements of the two ranges \[`first1`,
 `last1`) and \[`first2`, `last2`) into the range \[`result`,
 `result_last`), where `result_last` is
 `result + (last1 - first1) + (last2 - first2)`, such that the resulting
 range satisfies `is_sorted(result, result_last)` or
 `is_sorted(result, result_last, comp)`, respectively.
 *Returns:* `result + (last1 - first1) + (last2 - first2)`.
+*Complexity:* Let N = `(last1 - first1) + (last2 - first2)`:
+- For the overloads with no `ExecutionPolicy`, at most N - 1
   comparisons.
+- For the overloads with an `ExecutionPolicy`, 𝑂(N) comparisons.
 *Remarks:* Stable ([[algorithm.stable]]).
 ``` cpp
 template<class BidirectionalIterator>
   void inplace_merge(BidirectionalIterator first,
                      BidirectionalIterator middle,
                      BidirectionalIterator last);
+template<class ExecutionPolicy, class BidirectionalIterator>
+  void inplace_merge(ExecutionPolicy&& exec,
+                     BidirectionalIterator first,
+                     BidirectionalIterator middle,
+                     BidirectionalIterator last);
 template<class BidirectionalIterator, class Compare>
   void inplace_merge(BidirectionalIterator first,
                      BidirectionalIterator middle,
                      BidirectionalIterator last, Compare comp);
+template<class ExecutionPolicy, class BidirectionalIterator, class Compare>
+  void inplace_merge(ExecutionPolicy&& exec,
+                     BidirectionalIterator first,
+                     BidirectionalIterator middle,
+                     BidirectionalIterator last, Compare comp);
 ```
+*Requires:* The ranges \[`first`, `middle`) and \[`middle`, `last`)
+shall be sorted with respect to `operator<` or `comp`.
+`BidirectionalIterator` shall satisfy the requirements of
+`ValueSwappable` ([[swappable.requirements]]). The type of `*first`
+shall satisfy the requirements of `MoveConstructible`
+(Table  [[tab:moveconstructible]]) and of `MoveAssignable`
+(Table  [[tab:moveassignable]]).
 *Effects:* Merges two sorted consecutive ranges \[`first`, `middle`) and
 \[`middle`, `last`), putting the result of the merge into the range
 \[`first`, `last`). The resulting range will be in non-decreasing order;
 that is, for every iterator `i` in \[`first`, `last`) other than
 `first`, the condition `*i < *(i - 1)` or, respectively,
+`comp(*i, *(i - 1))` will be `false`.
+*Complexity:* Let N = `last - first`:
+- For the overloads with no `ExecutionPolicy`, if enough additional
+  memory is available, exactly N - 1 comparisons.
+- For the overloads with no `ExecutionPolicy` if no additional memory is
+  available, 𝑂(N log N) comparisons.
+- For the overloads with an `ExecutionPolicy`, 𝑂(N log N) comparisons.
 *Remarks:* Stable ([[algorithm.stable]]).
 ### Set operations on sorted structures <a id="alg.set.operations">[[alg.set.operations]]</a>
 ``` cpp
 template<class InputIterator1, class InputIterator2>
   bool includes(InputIterator1 first1, InputIterator1 last1,
                 InputIterator2 first2, InputIterator2 last2);
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
+  bool includes(ExecutionPolicy&& exec,
+                ForwardIterator1 first1, ForwardIterator1 last1,
+                ForwardIterator2 first2, ForwardIterator2 last2);
 template<class InputIterator1, class InputIterator2, class Compare>
   bool includes(InputIterator1 first1, InputIterator1 last1,
                 InputIterator2 first2, InputIterator2 last2,
                 Compare comp);
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Compare>
+  bool includes(ExecutionPolicy&& exec,
+                ForwardIterator1 first1, ForwardIterator1 last1,
+                ForwardIterator2 first2, ForwardIterator2 last2,
+                Compare comp);
 ```
 *Returns:* `true` if \[`first2`, `last2`) is empty or if every element
 in the range \[`first2`, `last2`) is contained in the range \[`first1`,
 `last1`). Returns `false` otherwise.
          class OutputIterator>
   OutputIterator
     set_union(InputIterator1 first1, InputIterator1 last1,
               InputIterator2 first2, InputIterator2 last2,
               OutputIterator result);
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
+         class ForwardIterator>
+  ForwardIterator
+    set_union(ExecutionPolicy&& exec,
+              ForwardIterator1 first1, ForwardIterator1 last1,
+              ForwardIterator2 first2, ForwardIterator2 last2,
+              ForwardIterator result);
 template<class InputIterator1, class InputIterator2,
          class OutputIterator, class Compare>
   OutputIterator
     set_union(InputIterator1 first1, InputIterator1 last1,
               InputIterator2 first2, InputIterator2 last2,
               OutputIterator result, Compare comp);
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
+         class ForwardIterator, class Compare>
+  ForwardIterator
+    set_union(ExecutionPolicy&& exec,
+              ForwardIterator1 first1, ForwardIterator1 last1,
+              ForwardIterator2 first2, ForwardIterator2 last2,
+              ForwardIterator result, Compare comp);
 ```
+*Requires:* The resulting range shall not overlap with either of the
+original ranges.
 *Effects:* Constructs a sorted union of the elements from the two
 ranges; that is, the set of elements that are present in one or both of
 the ranges.
 *Returns:* The end of the constructed range.
 *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
 comparisons.
          class OutputIterator>
   OutputIterator
     set_intersection(InputIterator1 first1, InputIterator1 last1,
                      InputIterator2 first2, InputIterator2 last2,
                      OutputIterator result);
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
+         class ForwardIterator>
+  ForwardIterator
+    set_intersection(ExecutionPolicy&& exec,
+                     ForwardIterator1 first1, ForwardIterator1 last1,
+                     ForwardIterator2 first2, ForwardIterator2 last2,
+                     ForwardIterator result);
 template<class InputIterator1, class InputIterator2,
          class OutputIterator, class Compare>
   OutputIterator
     set_intersection(InputIterator1 first1, InputIterator1 last1,
                      InputIterator2 first2, InputIterator2 last2,
                      OutputIterator result, Compare comp);
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
+         class ForwardIterator, class Compare>
+  ForwardIterator
+    set_intersection(ExecutionPolicy&& exec,
+                     ForwardIterator1 first1, ForwardIterator1 last1,
+                     ForwardIterator2 first2, ForwardIterator2 last2,
+                     ForwardIterator result, Compare comp);
 ```
+*Requires:* The resulting range shall not overlap with either of the
+original ranges.
 *Effects:* Constructs a sorted intersection of the elements from the two
 ranges; that is, the set of elements that are present in both of the
 ranges.
 *Returns:* The end of the constructed range.
 *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
 comparisons.
          class OutputIterator>
   OutputIterator
     set_difference(InputIterator1 first1, InputIterator1 last1,
                    InputIterator2 first2, InputIterator2 last2,
                    OutputIterator result);
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
+           class ForwardIterator>
+  ForwardIterator
+    set_difference(ExecutionPolicy&& exec,
+                   ForwardIterator1 first1, ForwardIterator1 last1,
+                   ForwardIterator2 first2, ForwardIterator2 last2,
+                   ForwardIterator result);
 template<class InputIterator1, class InputIterator2,
          class OutputIterator, class Compare>
   OutputIterator
     set_difference(InputIterator1 first1, InputIterator1 last1,
                    InputIterator2 first2, InputIterator2 last2,
                    OutputIterator result, Compare comp);
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
+         class ForwardIterator, class Compare>
+  ForwardIterator
+    set_difference(ExecutionPolicy&& exec,
+                   ForwardIterator1 first1, ForwardIterator1 last1,
+                   ForwardIterator2 first2, ForwardIterator2 last2,
+                   ForwardIterator result, Compare comp);
 ```
+*Requires:* The resulting range shall not overlap with either of the
+original ranges.
 *Effects:* Copies the elements of the range \[`first1`, `last1`) which
 are not present in the range \[`first2`, `last2`) to the range beginning
 at `result`. The elements in the constructed range are sorted.
 *Returns:* The end of the constructed range.
 *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
 comparisons.
          class OutputIterator>
   OutputIterator
     set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
                              InputIterator2 first2, InputIterator2 last2,
                              OutputIterator result);
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
+         class ForwardIterator>
+  ForwardIterator
+    set_symmetric_difference(ExecutionPolicy&& exec,
+                             ForwardIterator1 first1, ForwardIterator1 last1,
+                             ForwardIterator2 first2, ForwardIterator2 last2,
+                             ForwardIterator result);
 template<class InputIterator1, class InputIterator2,
          class OutputIterator, class Compare>
   OutputIterator
     set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
                              InputIterator2 first2, InputIterator2 last2,
                              OutputIterator result, Compare comp);
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
+         class ForwardIterator, class Compare>
+  ForwardIterator
+    set_symmetric_difference(ExecutionPolicy&& exec,
+                             ForwardIterator1 first1, ForwardIterator1 last1,
+                             ForwardIterator2 first2, ForwardIterator2 last2,
+                             ForwardIterator result, Compare comp);
 ```
+*Requires:* The resulting range shall not overlap with either of the
+original ranges.
 *Effects:* Copies the elements of the range \[`first1`, `last1`) that
 are not present in the range \[`first2`, `last2`), and the elements of
 the range \[`first2`, `last2`) that are not present in the range
 \[`first1`, `last1`) to the range beginning at `result`. The elements in
 the constructed range are sorted.
 *Returns:* The end of the constructed range.
 *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
 comparisons.
 \[`first2`, `last2`) if m < n.
 ### Heap operations <a id="alg.heap.operations">[[alg.heap.operations]]</a>
 A *heap* is a particular organization of elements in a range between two
+random access iterators \[`a`, `b`) such that:
+- With `N = b - a`, for all i, 0 < i < N,
+  `comp(a[\left \lfloor{\frac{i - 1}{2}}\right \rfloor], a[i])` is
+  `false`.
+- `*a` may be removed by `pop_heap()`, or a new element added by
+ `push_heap()`, in 𝑂(log N) time.
 These properties make heaps useful as priority queues.
 `make_heap()`
 template<class RandomAccessIterator, class Compare>
   void push_heap(RandomAccessIterator first, RandomAccessIterator last,
                  Compare comp);
 ```
 *Requires:* The range \[`first`, `last - 1`) shall be a valid heap. The
 type of `*first` shall satisfy the `MoveConstructible` requirements
+(Table  [[tab:moveconstructible]]) and the `MoveAssignable` requirements
+(Table  [[tab:moveassignable]]).
+*Effects:* Places the value in the location `last - 1` into the
+resulting heap \[`first`, `last`).
+*Complexity:* At most log(`last - first`) comparisons.
 #### `pop_heap` <a id="pop.heap">[[pop.heap]]</a>
 ``` cpp
 template<class RandomAccessIterator>
 *Requires:* The range \[`first`, `last`) shall be a valid non-empty
 heap. `RandomAccessIterator` shall satisfy the requirements of
 `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
 shall satisfy the requirements of `MoveConstructible`
+(Table  [[tab:moveconstructible]]) and of `MoveAssignable`
+(Table  [[tab:moveassignable]]).
 *Effects:* Swaps the value in the location `first` with the value in the
 location `last - 1` and makes \[`first`, `last - 1`) into a heap.
+*Complexity:* At most 2 log(`last - first`) comparisons.
 #### `make_heap` <a id="make.heap">[[make.heap]]</a>
 ``` cpp
 template<class RandomAccessIterator>
 template<class RandomAccessIterator, class Compare>
   void make_heap(RandomAccessIterator first, RandomAccessIterator last,
                  Compare comp);
 ```
 *Requires:* The type of `*first` shall satisfy the `MoveConstructible`
+requirements (Table  [[tab:moveconstructible]]) and the `MoveAssignable`
+requirements (Table  [[tab:moveassignable]]).
+*Effects:* Constructs a heap out of the range \[`first`, `last`).
+*Complexity:* At most 3(`last - first`) comparisons.
 #### `sort_heap` <a id="sort.heap">[[sort.heap]]</a>
 ``` cpp
 template<class RandomAccessIterator>
 template<class RandomAccessIterator, class Compare>
   void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
                  Compare comp);
 ```
 *Requires:* The range \[`first`, `last`) shall be a valid heap.
 `RandomAccessIterator` shall satisfy the requirements of
 `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
 shall satisfy the requirements of `MoveConstructible`
+(Table  [[tab:moveconstructible]]) and of `MoveAssignable`
+(Table  [[tab:moveassignable]]).
+*Effects:* Sorts elements in the heap \[`first`, `last`).
+*Complexity:* At most N log N comparisons, where N = `last - first`.
 #### `is_heap` <a id="is.heap">[[is.heap]]</a>
 ``` cpp
 template<class RandomAccessIterator>
   bool is_heap(RandomAccessIterator first, RandomAccessIterator last);
 ```
 *Returns:* `is_heap_until(first, last) == last`
+``` cpp
+template<class ExecutionPolicy, class RandomAccessIterator>
+  bool is_heap(ExecutionPolicy&& exec,
+               RandomAccessIterator first, RandomAccessIterator last);
+```
+*Returns:*
+`is_heap_until(std::forward<ExecutionPolicy>(exec), first, last) == last`
 ``` cpp
 template<class RandomAccessIterator, class Compare>
   bool is_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
 ```
 *Returns:* `is_heap_until(first, last, comp) == last`
+``` cpp
+template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
+  bool is_heap(ExecutionPolicy&& exec,
+               RandomAccessIterator first, RandomAccessIterator last, Compare comp);
+```
+*Returns:*
+``` cpp
+is_heap_until(std::forward<ExecutionPolicy>(exec), first, last, comp) == last
+```
 ``` cpp
 template<class RandomAccessIterator>
   RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last);
+template<class ExecutionPolicy, class RandomAccessIterator>
+  RandomAccessIterator is_heap_until(ExecutionPolicy&& exec,
+                                     RandomAccessIterator first, RandomAccessIterator last);
 template<class RandomAccessIterator, class Compare>
   RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last,
                                      Compare comp);
+template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
+  RandomAccessIterator is_heap_until(ExecutionPolicy&& exec,
+                                     RandomAccessIterator first, RandomAccessIterator last,
+                                     Compare comp);
 ```
+*Returns:* If `(last - first) < 2`, returns `last`. Otherwise, returns
+the last iterator `i` in \[`first`, `last`\] for which the range
 \[`first`, `i`) is a heap.
 *Complexity:* Linear.
 ### Minimum and maximum <a id="alg.min.max">[[alg.min.max]]</a>
 template<class T> constexpr const T& min(const T& a, const T& b);
 template<class T, class Compare>
   constexpr const T& min(const T& a, const T& b, Compare comp);
 ```
+*Requires:* For the first form, type `T` shall be `LessThanComparable`
+(Table  [[tab:lessthancomparable]]).
 *Returns:* The smaller value.
 *Remarks:* Returns the first argument when the arguments are equivalent.
+*Complexity:* Exactly one comparison.
 ``` cpp
 template<class T>
   constexpr T min(initializer_list<T> t);
 template<class T, class Compare>
   constexpr T min(initializer_list<T> t, Compare comp);
 ```
+*Requires:* `T` shall be `CopyConstructible` and `t.size() > 0`. For the
+first form, type `T` shall be `LessThanComparable`.
 *Returns:* The smallest value in the initializer_list.
 *Remarks:* Returns a copy of the leftmost argument when several
 arguments are equivalent to the smallest.
+*Complexity:* Exactly `t.size() - 1` comparisons.
 ``` cpp
 template<class T> constexpr const T& max(const T& a, const T& b);
 template<class T, class Compare>
   constexpr const T& max(const T& a, const T& b, Compare comp);
 ```
+*Requires:* For the first form, type `T` shall be `LessThanComparable`
+(Table  [[tab:lessthancomparable]]).
 *Returns:* The larger value.
 *Remarks:* Returns the first argument when the arguments are equivalent.
+*Complexity:* Exactly one comparison.
 ``` cpp
 template<class T>
   constexpr T max(initializer_list<T> t);
 template<class T, class Compare>
   constexpr T max(initializer_list<T> t, Compare comp);
 ```
+*Requires:* `T` shall be `CopyConstructible` and `t.size() > 0`. For the
+first form, type `T` shall be `LessThanComparable`.
 *Returns:* The largest value in the initializer_list.
 *Remarks:* Returns a copy of the leftmost argument when several
 arguments are equivalent to the largest.
+*Complexity:* Exactly `t.size() - 1` comparisons.
 ``` cpp
 template<class T> constexpr pair<const T&, const T&> minmax(const T& a, const T& b);
 template<class T, class Compare>
   constexpr pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp);
 ```
+*Requires:* For the first form, type `T` shall be `LessThanComparable`
+(Table  [[tab:lessthancomparable]]).
 *Returns:* `pair<const T&, const T&>(b, a)` if `b` is smaller than `a`,
 and `pair<const T&, const T&>(a, b)` otherwise.
 *Remarks:* Returns `pair<const T&, const T&>(a, b)` when the arguments
   constexpr pair<T, T> minmax(initializer_list<T> t);
 template<class T, class Compare>
   constexpr pair<T, T> minmax(initializer_list<T> t, Compare comp);
 ```
+*Requires:* `T` shall be `CopyConstructible` and `t.size() > 0`. For the
+first form, type `T` shall be `LessThanComparable`.
 *Returns:* `pair<T, T>(x, y)`, where `x` has the smallest and `y` has
 the largest value in the initializer list.
 *Remarks:* `x` is a copy of the leftmost argument when several arguments
 are equivalent to the smallest. `y` is a copy of the rightmost argument
 when several arguments are equivalent to the largest.
+*Complexity:* At most (3/2)`t.size()` applications of the corresponding
+predicate.
 ``` cpp
 template<class ForwardIterator>
+ constexpr ForwardIterator min_element(ForwardIterator first, ForwardIterator last);
+template<class ExecutionPolicy, class ForwardIterator>
+  ForwardIterator min_element(ExecutionPolicy&& exec,
+                              ForwardIterator first, ForwardIterator last);
 template<class ForwardIterator, class Compare>
+ constexpr ForwardIterator min_element(ForwardIterator first, ForwardIterator last,
+                                        Compare comp);
+template<class ExecutionPolicy, class ForwardIterator, class Compare>
+  ForwardIterator min_element(ExecutionPolicy&& exec,
+                              ForwardIterator first, ForwardIterator last,
                               Compare comp);
 ```
 *Returns:* The first iterator `i` in the range \[`first`, `last`) such
 that for every iterator `j` in the range \[`first`, `last`) the
 following corresponding conditions hold: `!(*j < *i)` or
 `comp(*j, *i) == false`. Returns `last` if `first == last`.
+*Complexity:* Exactly max(`last - first - 1`, 0) applications of the
 corresponding comparisons.
 ``` cpp
 template<class ForwardIterator>
+ constexpr ForwardIterator max_element(ForwardIterator first, ForwardIterator last);
+template<class ExecutionPolicy, class ForwardIterator>
+  ForwardIterator max_element(ExecutionPolicy&& exec,
+                              ForwardIterator first, ForwardIterator last);
 template<class ForwardIterator, class Compare>
+ constexpr ForwardIterator max_element(ForwardIterator first, ForwardIterator last,
+                                        Compare comp);
+template<class ExecutionPolicy, class ForwardIterator, class Compare>
+  ForwardIterator max_element(ExecutionPolicy&& exec,
+                              ForwardIterator first, ForwardIterator last,
                               Compare comp);
 ```
 *Returns:* The first iterator `i` in the range \[`first`, `last`) such
 that for every iterator `j` in the range \[`first`, `last`) the
 following corresponding conditions hold: `!(*i < *j)` or
 `comp(*i, *j) == false`. Returns `last` if `first == last`.
+*Complexity:* Exactly max(`last - first - 1`, 0) applications of the
 corresponding comparisons.
 ``` cpp
 template<class ForwardIterator>
+ constexpr pair<ForwardIterator, ForwardIterator>
     minmax_element(ForwardIterator first, ForwardIterator last);
+template<class ExecutionPolicy, class ForwardIterator>
   pair<ForwardIterator, ForwardIterator>
+    minmax_element(ExecutionPolicy&& exec,
+                   ForwardIterator first, ForwardIterator last);
+template<class ForwardIterator, class Compare>
+  constexpr pair<ForwardIterator, ForwardIterator>
     minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
+template<class ExecutionPolicy, class ForwardIterator, class Compare>
+  pair<ForwardIterator, ForwardIterator>
+    minmax_element(ExecutionPolicy&& exec,
+                   ForwardIterator first, ForwardIterator last, Compare comp);
 ```
 *Returns:* `make_pair(first, first)` if \[`first`, `last`) is empty,
 otherwise `make_pair(m, M)`, where `m` is the first iterator in
 \[`first`, `last`) such that no iterator in the range refers to a
+smaller element, and where `M` is the last iterator[^5] in \[`first`,
 `last`) such that no iterator in the range refers to a larger element.
+*Complexity:* At most
+$\max(\bigl\lfloor{\frac{3}{2}} (N-1)\bigr\rfloor, 0)$ applications of
+the corresponding predicate, where N is `last - first`.
+### Bounded value <a id="alg.clamp">[[alg.clamp]]</a>
+``` cpp
+template<class T>
+  constexpr const T& clamp(const T& v, const T& lo, const T& hi);
+template<class T, class Compare>
+  constexpr const T& clamp(const T& v, const T& lo, const T& hi, Compare comp);
+```
+*Requires:* The value of `lo` shall be no greater than `hi`. For the
+first form, type `T` shall be `LessThanComparable`
+(Table  [[tab:lessthancomparable]]).
+*Returns:* `lo` if `v` is less than `lo`, `hi` if `hi` is less than `v`,
+otherwise `v`.
+[*Note 1*: If NaN is avoided, `T` can be a floating-point
+type. — *end note*]
+*Complexity:* At most two comparisons.
 ### Lexicographical comparison <a id="alg.lex.comparison">[[alg.lex.comparison]]</a>
 ``` cpp
 template<class InputIterator1, class InputIterator2>
   bool
     lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
                             InputIterator2 first2, InputIterator2 last2);
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
+  bool
+    lexicographical_compare(ExecutionPolicy&& exec,
+                            ForwardIterator1 first1, ForwardIterator1 last1,
+                            ForwardIterator2 first2, ForwardIterator2 last2);
 template<class InputIterator1, class InputIterator2, class Compare>
   bool
     lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
                             InputIterator2 first2, InputIterator2 last2,
                             Compare comp);
+template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Compare>
+  bool
+    lexicographical_compare(ExecutionPolicy&& exec,
+                            ForwardIterator1 first1, ForwardIterator1 last1,
+                            ForwardIterator2 first2, ForwardIterator2 last2,
+                            Compare comp);
 ```
 *Returns:* `true` if the sequence of elements defined by the range
 \[`first1`, `last1`) is lexicographically less than the sequence of
 elements defined by the range \[`first2`, `last2`) and `false`
 otherwise.
+*Complexity:* At most 2 min(`last1 - first1`,  `last2 - first2`)
 applications of the corresponding comparison.
 *Remarks:* If two sequences have the same number of elements and their
+corresponding elements (if any) are equivalent, then neither sequence is
 lexicographically less than the other. If one sequence is a prefix of
 the other, then the shorter sequence is lexicographically less than the
 longer sequence. Otherwise, the lexicographical comparison of the
 sequences yields the same result as the comparison of the first
 corresponding pair of elements that are not equivalent.
+[*Example 1*:
+The following sample implementation satisfies these requirements:
 ``` cpp
+for ( ; first1 != last1 && first2 != last2 ; ++first1, (void) ++first2) {
   if (*first1 < *first2) return true;
   if (*first2 < *first1) return false;
 }
 return first1 == last1 && first2 != last2;
 ```
+— *end example*]
+[*Note 1*: An empty sequence is lexicographically less than any
+non-empty sequence, but not less than any empty sequence. — *end note*]
 ### Permutation generators <a id="alg.permutation.generators">[[alg.permutation.generators]]</a>
 ``` cpp
 template<class BidirectionalIterator>
 template<class BidirectionalIterator, class Compare>
   bool next_permutation(BidirectionalIterator first,
                         BidirectionalIterator last, Compare comp);
 ```
+*Requires:* `BidirectionalIterator` shall satisfy the requirements of
+`ValueSwappable` ([[swappable.requirements]]).
 *Effects:* Takes a sequence defined by the range \[`first`, `last`) and
 transforms it into the next permutation. The next permutation is found
 by assuming that the set of all permutations is lexicographically sorted
+with respect to `operator<` or `comp`.
+*Returns:* `true` if such a permutation exists. Otherwise, it transforms
+the sequence into the smallest permutation, that is, the ascendingly
+sorted one, and returns `false`.
 *Complexity:* At most `(last - first) / 2` swaps.
 ``` cpp
 template<class BidirectionalIterator>
 template<class BidirectionalIterator, class Compare>
   bool prev_permutation(BidirectionalIterator first,
                         BidirectionalIterator last, Compare comp);
 ```
+*Requires:* `BidirectionalIterator` shall satisfy the requirements of
+`ValueSwappable` ([[swappable.requirements]]).
 *Effects:* Takes a sequence defined by the range \[`first`, `last`) and
 transforms it into the previous permutation. The previous permutation is
 found by assuming that the set of all permutations is lexicographically
 sorted with respect to `operator<` or `comp`.
 *Returns:* `true` if such a permutation exists. Otherwise, it transforms
 the sequence into the largest permutation, that is, the descendingly
 sorted one, and returns `false`.
 *Complexity:* At most `(last - first) / 2` swaps.

Diff to HTML by rtfpessoa