Sorting
Algorithms
Collaboration diagram for Sorting:

## Modules

| Binary Search
| Heap
| Set Operations

## Functions

template<typename _Tp >
constexpr const _Tp & | std::clamp (const _Tp &__val, const _Tp &__lo, const _Tp &__hi)
template<typename _Tp , typename _Compare >
constexpr const _Tp & | std::clamp (const _Tp &__val, const _Tp &__lo, const _Tp &__hi, _Compare __comp)
template<typename _BidirectionalIterator >
void | std::inplace_merge (_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last)
template<typename _BidirectionalIterator , typename _Compare >
void | std::inplace_merge (_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Compare __comp)
template<typename _ForwardIterator >
constexpr bool | std::is_sorted (_ForwardIterator __first, _ForwardIterator __last)
template<typename _ForwardIterator , typename _Compare >
constexpr bool | std::is_sorted (_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
template<typename _ForwardIterator >
constexpr _ForwardIterator | std::is_sorted_until (_ForwardIterator __first, _ForwardIterator __last)
template<typename _ForwardIterator , typename _Compare >
constexpr _ForwardIterator | std::is_sorted_until (_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
template<typename _II1 , typename _II2 >
constexpr bool | std::lexicographical_compare (_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
template<typename _II1 , typename _II2 , typename _Compare >
constexpr bool | std::lexicographical_compare (_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2, _Compare __comp)
template<typename _Tp >
constexpr const _Tp & | std::max (const _Tp &__a, const _Tp &__b)
template<typename _Tp , typename _Compare >
constexpr const _Tp & | std::max (const _Tp &__a, const _Tp &__b, _Compare __comp)
template<typename _ForwardIterator >
constexpr _ForwardIterator | std::max_element (_ForwardIterator __first, _ForwardIterator __last)
template<typename _ForwardIterator , typename _Compare >
constexpr _ForwardIterator | std::max_element (_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
template<typename _InputIterator1 , typename _InputIterator2 , typename _OutputIterator >
constexpr _OutputIterator | std::merge (_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
template<typename _InputIterator1 , typename _InputIterator2 , typename _OutputIterator , typename _Compare >
constexpr _OutputIterator | std::merge (_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
template<typename _Tp >
constexpr const _Tp & | std::min (const _Tp &__a, const _Tp &__b)
template<typename _Tp , typename _Compare >
constexpr const _Tp & | std::min (const _Tp &__a, const _Tp &__b, _Compare __comp)
template<typename _ForwardIterator >
constexpr _ForwardIterator | std::min_element (_ForwardIterator __first, _ForwardIterator __last)
template<typename _ForwardIterator , typename _Compare >
constexpr _ForwardIterator | std::min_element (_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
template<typename _Tp >
constexpr pair< const _Tp &, const _Tp & > | std::minmax (const _Tp &__a, const _Tp &__b)
template<typename _Tp , typename _Compare >
constexpr pair< const _Tp &, const _Tp & > | std::minmax (const _Tp &__a, const _Tp &__b, _Compare __comp)
template<typename _ForwardIterator >
constexpr pair< _ForwardIterator, _ForwardIterator > | std::minmax_element (_ForwardIterator __first, _ForwardIterator __last)
template<typename _ForwardIterator , typename _Compare >
constexpr pair< _ForwardIterator, _ForwardIterator > | std::minmax_element (_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
template<typename _BidirectionalIterator >
constexpr bool | std::next_permutation (_BidirectionalIterator __first, _BidirectionalIterator __last)
template<typename _BidirectionalIterator , typename _Compare >
constexpr bool | std::next_permutation (_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
template<typename _RandomAccessIterator >
constexpr void | std::nth_element (_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last)
template<typename _RandomAccessIterator , typename _Compare >
constexpr void | std::nth_element (_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
template<typename _RandomAccessIterator >
constexpr void | std::partial_sort (_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
template<typename _RandomAccessIterator , typename _Compare >
constexpr void | std::partial_sort (_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp)
template<typename _InputIterator , typename _RandomAccessIterator >
constexpr _RandomAccessIterator | std::partial_sort_copy (_InputIterator __first, _InputIterator __last, _RandomAccessIterator __result_first, _RandomAccessIterator __result_last)
template<typename _InputIterator , typename _RandomAccessIterator , typename _Compare >
constexpr _RandomAccessIterator | std::partial_sort_copy (_InputIterator __first, _InputIterator __last, _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
template<typename _BidirectionalIterator >
constexpr bool | std::prev_permutation (_BidirectionalIterator __first, _BidirectionalIterator __last)
template<typename _BidirectionalIterator , typename _Compare >
constexpr bool | std::prev_permutation (_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
template<typename _RandomAccessIterator >
constexpr void | std::sort (_RandomAccessIterator __first, _RandomAccessIterator __last)
template<typename _RandomAccessIterator , typename _Compare >
constexpr void | std::sort (_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
template<typename _RandomAccessIterator >
void | std::stable_sort (_RandomAccessIterator __first, _RandomAccessIterator __last)
template<typename _RandomAccessIterator , typename _Compare >
void | std::stable_sort (_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)

## Detailed Description

## Function Documentation

## clamp() [1/2]

template<typename _Tp >

constexpr const _Tp & std::clamp | ( | const _Tp & | __val,
|  | const _Tp & | __lo,
|  | const _Tp & | __hi
| ) |  |

constexpr

Returns the value clamped between lo and hi.

Parameters

  __val | A value of arbitrary type.
  __lo | A lower limit of arbitrary type.
  __hi | An upper limit of arbitrary type.

Returns
  max(__val, __lo) if __val < __hi or min(__val, __hi) otherwise.

Definition at line 3656 of file stl_algo.h.

## clamp() [2/2]

template<typename _Tp , typename _Compare >

constexpr const _Tp & std::clamp | ( | const _Tp & | __val,
|  | const _Tp & | __lo,
|  | const _Tp & | __hi,
|  | _Compare | __comp
| ) |  |

constexpr

Returns the value clamped between lo and hi.

Parameters

  __val | A value of arbitrary type.
  __lo | A lower limit of arbitrary type.
  __hi | An upper limit of arbitrary type.
  __comp | A comparison functor.

Returns
  max(__val, __lo, __comp) if __comp(__val, __hi) or min(__val, __hi, __comp) otherwise.

Definition at line 3674 of file stl_algo.h.

## inplace_merge() [1/2]

template<typename _BidirectionalIterator >

void std::inplace_merge | ( | _BidirectionalIterator | __first,
|  | _BidirectionalIterator | __middle,
|  | _BidirectionalIterator | __last
| ) |  |

inline

Merges two sorted ranges in place.

Parameters

  __first | An iterator.
  __middle | Another iterator.
  __last | Another iterator.

Returns
  Nothing.

Merges two sorted and consecutive ranges, [__first,__middle) and [__middle,__last), and puts the result in [__first,__last). The output will be sorted. The sort is stable, that is, for equivalent elements in the two ranges, elements from the first range will always come before elements from the second.

If enough additional memory is available, this takes (__last-__first)-1 comparisons. Otherwise an NlogN algorithm is used, where N is distance(__first,__last).

Definition at line 2567 of file stl_algo.h.

## inplace_merge() [2/2]

template<typename _BidirectionalIterator , typename _Compare >

void std::inplace_merge | ( | _BidirectionalIterator | __first,
|  | _BidirectionalIterator | __middle,
|  | _BidirectionalIterator | __last,
|  | _Compare | __comp
| ) |  |

inline

Merges two sorted ranges in place.

Parameters

  __first | An iterator.
  __middle | Another iterator.
  __last | Another iterator.
  __comp | A functor to use for comparisons.

Returns
  Nothing.

Merges two sorted and consecutive ranges, [__first,__middle) and [middle,last), and puts the result in [__first,__last). The output will be sorted. The sort is stable, that is, for equivalent elements in the two ranges, elements from the first range will always come before elements from the second.

If enough additional memory is available, this takes (__last-__first)-1 comparisons. Otherwise an NlogN algorithm is used, where N is distance(__first,__last).

The comparison function should have the same effects on ordering as the function used for the initial sort.

Definition at line 2608 of file stl_algo.h.

## is_sorted() [1/2]

template<typename _ForwardIterator >

constexpr bool std::is_sorted | ( | _ForwardIterator | __first,
|  | _ForwardIterator | __last
| ) |  |

inline constexpr

Determines whether the elements of a sequence are sorted.

Parameters

  __first | An iterator.
  __last | Another iterator.

Returns
  True if the elements are sorted, false otherwise.

Definition at line 3204 of file stl_algo.h.

## is_sorted() [2/2]

template<typename _ForwardIterator , typename _Compare >

constexpr bool std::is_sorted | ( | _ForwardIterator | __first,
|  | _ForwardIterator | __last,
|  | _Compare | __comp
| ) |  |

inline constexpr

Determines whether the elements of a sequence are sorted according to a comparison functor.

Parameters

  __first | An iterator.
  __last | Another iterator.
  __comp | A comparison functor.

Returns
  True if the elements are sorted, false otherwise.

Definition at line 3219 of file stl_algo.h.

## is_sorted_until() [1/2]

template<typename _ForwardIterator >

constexpr _ForwardIterator std::is_sorted_until | ( | _ForwardIterator | __first,
|  | _ForwardIterator | __last
| ) |  |

inline constexpr

Determines the end of a sorted sequence.

Parameters

  __first | An iterator.
  __last | Another iterator.

Returns
  An iterator pointing to the last iterator i in [__first, __last) for which the range [__first, i) is sorted.

Definition at line 3250 of file stl_algo.h.

## is_sorted_until() [2/2]

template<typename _ForwardIterator , typename _Compare >

constexpr _ForwardIterator std::is_sorted_until | ( | _ForwardIterator | __first,
|  | _ForwardIterator | __last,
|  | _Compare | __comp
| ) |  |

inline constexpr

Determines the end of a sorted sequence using comparison functor.

Parameters

  __first | An iterator.
  __last | Another iterator.
  __comp | A comparison functor.

Returns
  An iterator pointing to the last iterator i in [__first, __last) for which the range [__first, i) is sorted.

Definition at line 3275 of file stl_algo.h.

## lexicographical_compare() [1/2]

template<typename _II1 , typename _II2 >

constexpr bool std::lexicographical_compare | ( | _II1 | __first1,
|  | _II1 | __last1,
|  | _II2 | __first2,
|  | _II2 | __last2
| ) |  |

inline constexpr

Performs dictionary comparison on ranges.

Parameters

  __first1 | An input iterator.
  __last1 | An input iterator.
  __first2 | An input iterator.
  __last2 | An input iterator.

Returns
  A boolean true or false.

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). Returns false otherwise. (Quoted from [25.3.8]/1.) If the iterators are all character pointers, then this is an inline call to `memcmp`.

Definition at line 1732 of file stl_algobase.h.

## lexicographical_compare() [2/2]

template<typename _II1 , typename _II2 , typename _Compare >

constexpr bool std::lexicographical_compare | ( | _II1 | __first1,
|  | _II1 | __last1,
|  | _II2 | __first2,
|  | _II2 | __last2,
|  | _Compare | __comp
| ) |  |

inline constexpr

Performs dictionary comparison on ranges.

Parameters

  __first1 | An input iterator.
  __last1 | An input iterator.
  __first2 | An input iterator.
  __last2 | An input iterator.
  __comp | A comparison functor.

Returns
  A boolean true or false.

The same as the four-parameter `lexicographical_compare`, but uses the comp parameter instead of `<`.

Definition at line 1767 of file stl_algobase.h.

## max() [1/2]

template<typename _Tp >

constexpr const _Tp & std::max | ( | const _Tp & | __a,
|  | const _Tp & | __b
| ) |  |

inline constexpr

This does what you think it does.

Parameters

  __a | A thing of arbitrary type.
  __b | Another thing of arbitrary type.

Returns
  The greater of the parameters.

This is the simple classic generic implementation. It will work on temporary expressions, since they are only evaluated once, unlike a preprocessor macro.

Definition at line 254 of file stl_algobase.h.

Referenced by __gnu_parallel::__parallel_nth_element(), std::_Deque_base< _Tp, _Alloc >::_M_initialize_map(), std::deque< _Tp, _Alloc >::_M_reallocate_map(), std::discard_block_engine< _RandomNumberEngine, __p, __r >::max(), std::shuffle_order_engine< _RandomNumberEngine, __k >::max(), __gnu_parallel::multiseq_selection(), std::shuffle_order_engine< _RandomNumberEngine, __k >::operator()(), and std::basic_stringbuf< _CharT, _Traits, _Alloc >::overflow().

## max() [2/2]

template<typename _Tp , typename _Compare >

constexpr const _Tp & std::max | ( | const _Tp & | __a,
|  | const _Tp & | __b,
|  | _Compare | __comp
| ) |  |

inline constexpr

This does what you think it does.

Parameters

  __a | A thing of arbitrary type.
  __b | Another thing of arbitrary type.
  __comp | A comparison functor.

Returns
  The greater of the parameters.

This will work on temporary expressions, since they are only evaluated once, unlike a preprocessor macro.

Definition at line 300 of file stl_algobase.h.

## max_element() [1/2]

template<typename _ForwardIterator >

constexpr _ForwardIterator std::max_element | ( | _ForwardIterator | __first,
|  | _ForwardIterator | __last
| ) |  |

inline constexpr

Return the maximum element in a range.

Parameters

  __first | Start of range.
  __last | End of range.

Returns
  Iterator referencing the first instance of the largest value.

Definition at line 5703 of file stl_algo.h.

## max_element() [2/2]

template<typename _ForwardIterator , typename _Compare >

constexpr _ForwardIterator std::max_element | ( | _ForwardIterator | __first,
|  | _ForwardIterator | __last,
|  | _Compare | __comp
| ) |  |

inline constexpr

Return the maximum element in a range using comparison functor.

Parameters

  __first | Start of range.
  __last | End of range.
  __comp | Comparison functor.

Returns
  Iterator referencing the first instance of the largest value according to __comp.

Definition at line 5728 of file stl_algo.h.

## merge() [1/2]

template<typename _InputIterator1 , typename _InputIterator2 , typename _OutputIterator >

constexpr _OutputIterator std::merge | ( | _InputIterator1 | __first1,
|  | _InputIterator1 | __last1,
|  | _InputIterator2 | __first2,
|  | _InputIterator2 | __last2,
|  | _OutputIterator | __result
| ) |  |

inline constexpr

Merges two sorted ranges.

Parameters

  __first1 | An iterator.
  __first2 | Another iterator.
  __last1 | Another iterator.
  __last2 | Another iterator.
  __result | An iterator pointing to the end of the merged range.

Returns
  An output iterator equal to `__result` + (__last1 - __first1)
  - (__last2 - __first2).

Merges the ranges ``[__first1,__last1) and ``[__first2,__last2) into the sorted range ``[__result, __result + (__last1-__first1) + (__last2-__first2)). Both input ranges must be sorted, and the output range must not overlap with either of the input ranges. The sort is stable, that is, for equivalent elements in the two ranges, elements from the first range will always come before elements from the second.

Definition at line 4927 of file stl_algo.h.

## merge() [2/2]

template<typename _InputIterator1 , typename _InputIterator2 , typename _OutputIterator , typename _Compare >

constexpr _OutputIterator std::merge | ( | _InputIterator1 | __first1,
|  | _InputIterator1 | __last1,
|  | _InputIterator2 | __first2,
|  | _InputIterator2 | __last2,
|  | _OutputIterator | __result,
|  | _Compare | __comp
| ) |  |

inline constexpr

Merges two sorted ranges.

Parameters

  __first1 | An iterator.
  __first2 | Another iterator.
  __last1 | Another iterator.
  __last2 | Another iterator.
  __result | An iterator pointing to the end of the merged range.
  __comp | A functor to use for comparisons.

Returns
  An output iterator equal to `__result` + (__last1 - __first1)
  - (__last2 - __first2).

Merges the ranges ``[__first1,__last1) and ``[__first2,__last2) into the sorted range ``[__result, __result + (__last1-__first1) + (__last2-__first2)). Both input ranges must be sorted, and the output range must not overlap with either of the input ranges. The sort is stable, that is, for equivalent elements in the two ranges, elements from the first range will always come before elements from the second.

The comparison function should have the same effects on ordering as the function used for the initial sort.

Definition at line 4978 of file stl_algo.h.

## min() [1/2]

template<typename _Tp >

constexpr const _Tp & std::min | ( | const _Tp & | __a,
|  | const _Tp & | __b
| ) |  |

inline constexpr

This does what you think it does.

Parameters

  __a | A thing of arbitrary type.
  __b | Another thing of arbitrary type.

Returns
  The lesser of the parameters.

This is the simple classic generic implementation. It will work on temporary expressions, since they are only evaluated once, unlike a preprocessor macro.

Definition at line 230 of file stl_algobase.h.

Referenced by std::basic_istream< char >::sentry::sentry(), __gnu_parallel::__parallel_random_shuffle_drs(), __gnu_parallel::__parallel_sort_qs_divide(), std::__sample(), __gnu_parallel::__search_template(), __gnu_parallel::__sequential_random_shuffle(), __gnu_cxx::__versa_string< _CharT, _Traits, _Alloc, _Base >::compare(), std::basic_string< _CharT, _Traits, _Alloc >::compare(), std::generate_canonical(), std::discard_block_engine< _RandomNumberEngine, __p, __r >::min(), std::shuffle_order_engine< _RandomNumberEngine, __k >::min(), std::shuffle_order_engine< _RandomNumberEngine, __k >::operator()(), std::basic_stringbuf< _CharT, _Traits, _Alloc >::overflow(), std::basic_filebuf< _CharT, std::char_traits< _CharT > >::seekpos(), std::basic_streambuf< _CharT, _Traits >::xsgetn(), std::basic_filebuf< _CharT, _Traits >::xsputn(), and std::basic_streambuf< _CharT, _Traits >::xsputn().

## min() [2/2]

template<typename _Tp , typename _Compare >

constexpr const _Tp & std::min | ( | const _Tp & | __a,
|  | const _Tp & | __b,
|  | _Compare | __comp
| ) |  |

inline constexpr

This does what you think it does.

Parameters

  __a | A thing of arbitrary type.
  __b | Another thing of arbitrary type.
  __comp | A comparison functor.

Returns
  The lesser of the parameters.

This will work on temporary expressions, since they are only evaluated once, unlike a preprocessor macro.

Definition at line 278 of file stl_algobase.h.

## min_element() [1/2]

template<typename _ForwardIterator >

constexpr _ForwardIterator std::min_element | ( | _ForwardIterator | __first,
|  | _ForwardIterator | __last
| ) |  |

inline constexpr

Return the minimum element in a range.

Parameters

  __first | Start of range.
  __last | End of range.

Returns
  Iterator referencing the first instance of the smallest value.

Definition at line 5639 of file stl_algo.h.

## min_element() [2/2]

template<typename _ForwardIterator , typename _Compare >

constexpr _ForwardIterator std::min_element | ( | _ForwardIterator | __first,
|  | _ForwardIterator | __last,
|  | _Compare | __comp
| ) |  |

inline constexpr

Return the minimum element in a range using comparison functor.

Parameters

  __first | Start of range.
  __last | End of range.
  __comp | Comparison functor.

Returns
  Iterator referencing the first instance of the smallest value according to __comp.

Definition at line 5664 of file stl_algo.h.

## minmax() [1/2]

template<typename _Tp >

constexpr pair< const _Tp &, const _Tp & > std::minmax | ( | const _Tp & | __a,
|  | const _Tp & | __b
| ) |  |

inline constexpr

Determines min and max at once as an ordered pair.

Parameters

  __a | A thing of arbitrary type.
  __b | Another thing of arbitrary type.

Returns
  A pair(__b, __a) if __b is smaller than __a, pair(__a, __b) otherwise.

Definition at line 3301 of file stl_algo.h.

## minmax() [2/2]

template<typename _Tp , typename _Compare >

constexpr pair< const _Tp &, const _Tp & > std::minmax | ( | const _Tp & | __a,
|  | const _Tp & | __b,
|  | _Compare | __comp
| ) |  |

inline constexpr

Determines min and max at once as an ordered pair.

Parameters

  __a | A thing of arbitrary type.
  __b | Another thing of arbitrary type.
  __comp | A comparison functor .

Returns
  A pair(__b, __a) if __b is smaller than __a, pair(__a, __b) otherwise.

Definition at line 3322 of file stl_algo.h.

## minmax_element() [1/2]

template<typename _ForwardIterator >

constexpr pair<_ForwardIterator, _ForwardIterator> std::minmax_element | ( | _ForwardIterator | __first,
|  | _ForwardIterator | __last
| ) |  |

inline constexpr

Return a pair of iterators pointing to the minimum and maximum elements in a range.

Parameters

  __first | Start of range.
  __last | End of range.

Returns
  make_pair(m, M), where m is the first iterator i in [__first, __last) such that no other element in the range is smaller, and where M is the last iterator i in [__first, __last) such that no other element in the range is larger.

Definition at line 3402 of file stl_algo.h.

## minmax_element() [2/2]

template<typename _ForwardIterator , typename _Compare >

constexpr pair<_ForwardIterator, _ForwardIterator> std::minmax_element | ( | _ForwardIterator | __first,
|  | _ForwardIterator | __last,
|  | _Compare | __comp
| ) |  |

inline constexpr

Return a pair of iterators pointing to the minimum and maximum elements in a range.

Parameters

  __first | Start of range.
  __last | End of range.
  __comp | Comparison functor.

Returns
  make_pair(m, M), where m is the first iterator i in [__first, __last) such that no other element in the range is smaller, and where M is the last iterator i in [__first, __last) such that no other element in the range is larger.

Definition at line 3430 of file stl_algo.h.

## next_permutation() [1/2]

template<typename _BidirectionalIterator >

constexpr bool std::next_permutation | ( | _BidirectionalIterator | __first,
|  | _BidirectionalIterator | __last
| ) |  |

inline constexpr

Permute range into the next dictionary ordering.

Parameters

  __first | Start of range.
  __last | End of range.

Returns
  False if wrapped to first permutation, true otherwise.

Treats all permutations of the range as a set of dictionary sorted sequences. Permutes the current sequence into the next one of this set. Returns true if there are more sequences to generate. If the sequence is the largest of the set, the smallest is generated and false returned.

Definition at line 2952 of file stl_algo.h.

## next_permutation() [2/2]

template<typename _BidirectionalIterator , typename _Compare >

constexpr bool std::next_permutation | ( | _BidirectionalIterator | __first,
|  | _BidirectionalIterator | __last,
|  | _Compare | __comp
| ) |  |

inline constexpr

Permute range into the next dictionary ordering using comparison functor.

Parameters

  __first | Start of range.
  __last | End of range.
  __comp | A comparison functor.

Returns
  False if wrapped to first permutation, true otherwise.

Treats all permutations of the range [__first,__last) as a set of dictionary sorted sequences ordered by `__comp`. Permutes the current sequence into the next one of this set. Returns true if there are more sequences to generate. If the sequence is the largest of the set, the smallest is generated and false returned.

Definition at line 2985 of file stl_algo.h.

## nth_element() [1/2]

template<typename _RandomAccessIterator >

constexpr void std::nth_element | ( | _RandomAccessIterator | __first,
|  | _RandomAccessIterator | __nth,
|  | _RandomAccessIterator | __last
| ) |  |

inline constexpr

Sort a sequence just enough to find a particular position.

Parameters

  __first | An iterator.
  __nth | Another iterator.
  __last | Another iterator.

Returns
  Nothing.

Rearranges the elements in the range ``[__first,__last) so that `*__nth` is the same element that would have been in that position had the whole sequence been sorted. The elements either side of `*__nth` are not completely sorted, but for any iterator i in the range ``[__first,__nth) and any iterator j in the range ``[__nth,__last) it holds that *j < *i is false.

Definition at line 4754 of file stl_algo.h.

## nth_element() [2/2]

template<typename _RandomAccessIterator , typename _Compare >

constexpr void std::nth_element | ( | _RandomAccessIterator | __first,
|  | _RandomAccessIterator | __nth,
|  | _RandomAccessIterator | __last,
|  | _Compare | __comp
| ) |  |

inline constexpr

Sort a sequence just enough to find a particular position using a predicate for comparison.

Parameters

  __first | An iterator.
  __nth | Another iterator.
  __last | Another iterator.
  __comp | A comparison functor.

Returns
  Nothing.

Rearranges the elements in the range ``[__first,__last) so that `*__nth` is the same element that would have been in that position had the whole sequence been sorted. The elements either side of `*__nth` are not completely sorted, but for any iterator i in the range ``[__first,__nth) and any iterator j in the range ``[__nth,__last) it holds that `__comp(*j,*i)` is false.

Definition at line 4794 of file stl_algo.h.

## partial_sort() [1/2]

template<typename _RandomAccessIterator >

constexpr void std::partial_sort | ( | _RandomAccessIterator | __first,
|  | _RandomAccessIterator | __middle,
|  | _RandomAccessIterator | __last
| ) |  |

inline constexpr

Sort the smallest elements of a sequence.

Parameters

  __first | An iterator.
  __middle | Another iterator.
  __last | Another iterator.

Returns
  Nothing.

Sorts the smallest ``(__middle-__first) elements in the range ``[first,last) and moves them to the range ``[__first,__middle). The order of the remaining elements in the range ``[__middle,__last) is undefined. After the sort if i and j are iterators in the range ``[__first,__middle) such that i precedes j and k is an iterator in the range ``[__middle,__last) then *j<*i and *k<*i are both false.

Definition at line 4678 of file stl_algo.h.

## partial_sort() [2/2]

template<typename _RandomAccessIterator , typename _Compare >

constexpr void std::partial_sort | ( | _RandomAccessIterator | __first,
|  | _RandomAccessIterator | __middle,
|  | _RandomAccessIterator | __last,
|  | _Compare | __comp
| ) |  |

inline constexpr

Sort the smallest elements of a sequence using a predicate for comparison.

Parameters

  __first | An iterator.
  __middle | Another iterator.
  __last | Another iterator.
  __comp | A comparison functor.

Returns
  Nothing.

Sorts the smallest ``(__middle-__first) elements in the range ``[__first,__last) and moves them to the range ``[__first,__middle). The order of the remaining elements in the range ``[__middle,__last) is undefined. After the sort if i and j are iterators in the range ``[__first,__middle) such that i precedes j and k is an iterator in the range ``[__middle,__last) then `*__comp`(j,*i) and `__comp(*k,*i)` are both false.

Definition at line 4717 of file stl_algo.h.

## partial_sort_copy() [1/2]

template<typename _InputIterator , typename _RandomAccessIterator >

constexpr _RandomAccessIterator std::partial_sort_copy | ( | _InputIterator | __first,
|  | _InputIterator | __last,
|  | _RandomAccessIterator | __result_first,
|  | _RandomAccessIterator | __result_last
| ) |  |

inline constexpr

Copy the smallest elements of a sequence.

Parameters

  __first | An iterator.
  __last | Another iterator.
  __result_first | A random-access iterator.
  __result_last | Another random-access iterator.

Returns
  An iterator indicating the end of the resulting sequence.

Copies and sorts the smallest N values from the range ``[__first,__last) to the range beginning at `__result_first`, where the number of elements to be copied, `N`, is the smaller of ``(__last-__first) and ``(__result_last-__result_first). After the sort if i and j are iterators in the range ``[__result_first,__result_first+N) such that i precedes j then *j<*i is false. The value returned is `__result_first+N`.

Definition at line 1713 of file stl_algo.h.

## partial_sort_copy() [2/2]

template<typename _InputIterator , typename _RandomAccessIterator , typename _Compare >

constexpr _RandomAccessIterator std::partial_sort_copy | ( | _InputIterator | __first,
|  | _InputIterator | __last,
|  | _RandomAccessIterator | __result_first,
|  | _RandomAccessIterator | __result_last,
|  | _Compare | __comp
| ) |  |

inline constexpr

Copy the smallest elements of a sequence using a predicate for comparison.

Parameters

  __first | An input iterator.
  __last | Another input iterator.
  __result_first | A random-access iterator.
  __result_last | Another random-access iterator.
  __comp | A comparison functor.

Returns
  An iterator indicating the end of the resulting sequence.

Copies and sorts the smallest N values from the range ``[__first,__last) to the range beginning at `result_first`, where the number of elements to be copied, `N`, is the smaller of ``(__last-__first) and ``(__result_last-__result_first). After the sort if i and j are iterators in the range ``[__result_first,__result_first+N) such that i precedes j then `__comp(*j,*i)` is false. The value returned is `__result_first+N`.

Definition at line 1764 of file stl_algo.h.

## prev_permutation() [1/2]

template<typename _BidirectionalIterator >

constexpr bool std::prev_permutation | ( | _BidirectionalIterator | __first,
|  | _BidirectionalIterator | __last
| ) |  |

inline constexpr

Permute range into the previous dictionary ordering.

Parameters

  __first | Start of range.
  __last | End of range.

Returns
  False if wrapped to last permutation, true otherwise.

Treats all permutations of the range as a set of dictionary sorted sequences. Permutes the current sequence into the previous one of this set. Returns true if there are more sequences to generate. If the sequence is the smallest of the set, the largest is generated and false returned.

Definition at line 3055 of file stl_algo.h.

## prev_permutation() [2/2]

template<typename _BidirectionalIterator , typename _Compare >

constexpr bool std::prev_permutation | ( | _BidirectionalIterator | __first,
|  | _BidirectionalIterator | __last,
|  | _Compare | __comp
| ) |  |

inline constexpr

Permute range into the previous dictionary ordering using comparison functor.

Parameters

  __first | Start of range.
  __last | End of range.
  __comp | A comparison functor.

Returns
  False if wrapped to last permutation, true otherwise.

Treats all permutations of the range [__first,__last) as a set of dictionary sorted sequences ordered by `__comp`. Permutes the current sequence into the previous one of this set. Returns true if there are more sequences to generate. If the sequence is the smallest of the set, the largest is generated and false returned.

Definition at line 3088 of file stl_algo.h.

## sort() [1/2]

template<typename _RandomAccessIterator >

constexpr void std::sort | ( | _RandomAccessIterator | __first,
|  | _RandomAccessIterator | __last
| ) |  |

inline constexpr

Sort the elements of a sequence.

Parameters

  __first | An iterator.
  __last | Another iterator.

Returns
  Nothing.

Sorts the elements in the range ``[__first,__last) in ascending order, such that for each iterator i in the range ``[__first,__last-1),
*(i+1)<*i is false.

The relative ordering of equivalent elements is not preserved, use `stable_sort()` if this is needed.

Definition at line 4832 of file stl_algo.h.

## sort() [2/2]

template<typename _RandomAccessIterator , typename _Compare >

constexpr void std::sort | ( | _RandomAccessIterator | __first,
|  | _RandomAccessIterator | __last,
|  | _Compare | __comp
| ) |  |

inline constexpr

Sort the elements of a sequence using a predicate for comparison.

Parameters

  __first | An iterator.
  __last | Another iterator.
  __comp | A comparison functor.

Returns
  Nothing.

Sorts the elements in the range ``[__first,__last) in ascending order, such that `__comp`(*(i+1),*i) is false for every iterator i in the range ``[__first,__last-1).

The relative ordering of equivalent elements is not preserved, use `stable_sort()` if this is needed.

Definition at line 4863 of file stl_algo.h.

## stable_sort() [1/2]

template<typename _RandomAccessIterator >

void std::stable_sort | ( | _RandomAccessIterator | __first,
|  | _RandomAccessIterator | __last
| ) |  |

inline

Sort the elements of a sequence, preserving the relative order of equivalent elements.

Parameters

  __first | An iterator.
  __last | Another iterator.

Returns
  Nothing.

Sorts the elements in the range ``[__first,__last) in ascending order, such that for each iterator `i` in the range ``[__first,__last-1), `*`(i+1)<*i is false.

The relative ordering of equivalent elements is preserved, so any two elements `x` and `y` in the range ``[__first,__last) such that `x<y` is false and `y<x` is false will have the same relative ordering after calling `stable_sort()`.

Definition at line 5046 of file stl_algo.h.

## stable_sort() [2/2]

template<typename _RandomAccessIterator , typename _Compare >

void std::stable_sort | ( | _RandomAccessIterator | __first,
|  | _RandomAccessIterator | __last,
|  | _Compare | __comp
| ) |  |

inline

Sort the elements of a sequence using a predicate for comparison, preserving the relative order of equivalent elements.

Parameters

  __first | An iterator.
  __last | Another iterator.
  __comp | A comparison functor.

Returns
  Nothing.

Sorts the elements in the range ``[__first,__last) in ascending order, such that for each iterator `i` in the range ``[__first,__last-1), `__comp`(*(i+1),*i) is false.

The relative ordering of equivalent elements is preserved, so any two elements `x` and `y` in the range ``[__first,__last) such that `__comp(x,y)` is false and `__comp(y,x)` is false will have the same relative ordering after calling `stable_sort()`.

Definition at line 5080 of file stl_algo.h.