SORTING_ALGORITHMS(3)

💅 Sorting Algorithms(3) 💅

okay so this is Sorting Algorithms(3) from the Library Functions Manual, and bestie… she is a whole saga. It's giving "the entire <algorithm> greatest-hits album, deluxe edition" and we're gonna get through it together, one template at a time. Grab a boba, get comfy. 🧋✨

🎀 NAME 🎀

Sorting Algorithms —

(and yeah, the bit after the dash is literally empty. no thoughts, head empty, and honestly? iconic. 💀)

🧩 Modules 🧩

three little module families live under this umbrella, and they're all linked in:

Set Operation Algorithms
Binary Search Algorithms
Heap Algorithms

📜 Functions 📜

the full cast list, no cuts, no skips — every single overload is a main character and yes you need all of them:

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

✨ Function Documentation ✨

okay NOW we get into the actual tea — every function, what it does, its params, and where it lives in the source. buckle up bestie, we're going one by one. 🫶

🌸 `std::inplace_merge` (the one with a comparator)

template<typename _BidirectionalIterator , typename _Compare > void std::inplace_merge (_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Compare __comp)

[inline]

Merges two sorted ranges in place. no cap, that's the whole vibe.

Parameters:

first — an iterator.
middle — another iterator.
last — another iterator.
comp — a functor to use for comparisons.

Returns: nothing.

so what it actually does: it merges two sorted and consecutive ranges, [first,middle) and [middle,last), and puts the result in [first,last). the output will be sorted. and the sort is stable — meaning for equivalent elements in the two ranges, elements from the first range will always come before elements from the second. that's the whole point, that's the slay. 👑

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. (fr fr, don't switch up your comparator halfway through, that's chaos.)

Definition at line 3185 of file stl_algo.h.

References: std::__merge_adaptive(), std::__merge_without_buffer(), std::_Temporary_buffer< _ForwardIterator, _Tp >::begin(), std::distance(), and std::_Temporary_buffer< _ForwardIterator, _Tp >::size().

🦋 `std::inplace_merge` (no comparator, living simply)

template<typename _BidirectionalIterator > void std::inplace_merge (_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last)

[inline]

Merges two sorted ranges in place. same energy, one less argument.

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, and the sort is stable — 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 3130 of file stl_algo.h.

🎀 `std::is_sorted` (with comparator)

template<typename _ForwardIterator , typename _Compare > bool std::is_sorted (_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)

[inline]

determines whether the elements of a sequence are sorted according to a comparison functor. literally the vibe check for your container ✨

Parameters:

first — an iterator.
last — another iterator.
comp — a comparison functor.

Returns: true if the elements are sorted, false otherwise.

Definition at line 3886 of file stl_algo.h.

References: std::is_sorted_until().

🦋 `std::is_sorted` (no comparator)

template<typename _ForwardIterator > bool std::is_sorted (_ForwardIterator __first, _ForwardIterator __last)

[inline]

determines whether the elements of a sequence are sorted. simple as that.

Parameters:

first — an iterator.
last — another iterator.

Returns: true if the elements are sorted, false otherwise.

Definition at line 3872 of file stl_algo.h.

References: std::is_sorted_until().

🍓 `std::is_sorted_until` (with comparator)

template<typename _ForwardIterator , typename _Compare > _ForwardIterator std::is_sorted_until (_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)

[inline]

determines the end of a sorted sequence using a comparison functor. it's giving "where exactly does the sorted part stop??" 🔍

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 3929 of file stl_algo.h.

Referenced by std::is_sorted().

🧚 `std::is_sorted_until` (no comparator)

template<typename _ForwardIterator > _ForwardIterator std::is_sorted_until (_ForwardIterator __first, _ForwardIterator __last)

[inline]

determines the end of a sorted sequence. same as above, default comparisons, no extra credit.

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 3900 of file stl_algo.h.

🫶 `std::lexicographical_compare` (with comparator)

template<typename _II1 , typename _II2 , typename _Compare > bool std::lexicographical_compare (_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2, _Compare __comp)

[inline]

performs 'dictionary' comparison on ranges.

Okay bestie, picking up right where we left off — the comp-flavored lexicographical_compare overload is serving the exact same energy as before, just with a custom comparison flex 💅

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 1050 of file stl_algobase.h.

Referenced by std::operator<().

✨ `std::lexicographical_compare` — the dictionary-comparison icon ✨

template<typename _II1 , typename _II2 > bool std::lexicographical_compare
    (_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) [inline]

Performs 'dictionary' comparison on ranges. So yes, it’s giving “compare these two ranges like words in a dictionary” realness 🔥

Parameters:

first1 — an input iterator.
last1 — an input iterator.
first2 — an input iterator.
last2 — an input iterator.

Returns: a boolean true or false.

Definition at line 1015 of file stl_algobase.h.

🌸 `std::max` — the `comp` overload 🌸

template<typename _Tp , typename _Compare > const _Tp & std::max (const _Tp
    & __a, const _Tp & __b, _Compare __comp) [inline]

This does what you think it does. No cap.

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 253 of file stl_algobase.h.

💖 `std::max` — the classic ✨

template<typename _Tp > const _Tp & std::max (const _Tp & __a, const _Tp &
    __b) [inline]

This does what you think it does. Again. Iconic behavior.

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 209 of file stl_algobase.h.

Referenced by std::tr1::__detail::__bessel_jn(), std::tr1::__detail::__ellint_rc(), std::tr1::__detail::__ellint_rd(), std::tr1::__detail::__ellint_rf(), std::tr1::__detail::__ellint_rj(), std::deque< _Tp, _Alloc >::_M_reallocate_map(), std::binomial_distribution< _IntType, _RealType >::operator()(), std::poisson_distribution< _IntType, _RealType >::operator()(), and std::basic_stringbuf< _CharT, _Traits, _Alloc >::overflow().

🦋 `std::max_element` — maximum-finding with a functor 🦋

template<typename _ForwardIterator , typename _Compare > _ForwardIterator
    std::max_element (_ForwardIterator __first, _ForwardIterator __last,
    _Compare __comp) [inline]

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 6070 of file stl_algo.h.

Referenced by std::valarray< _Tp >::max().

⭐ `std::max_element` — the simple max hunt ⭐

template<typename _ForwardIterator > _ForwardIterator std::max_element
    (_ForwardIterator __first, _ForwardIterator __last) [inline]

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 6042 of file stl_algo.h.

🎀 `std::merge` — with comparison functor 🎀

template<typename _InputIterator1 , typename _InputIterator2 , typename
    _OutputIterator , typename _Compare > _OutputIterator std::merge
    (_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2
    __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare
    __comp) [inline]

Merges two sorted ranges. It’s giving “glue these two sorted situations together” and honestly? Obsessed.

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 iterator pointing to the first element 'not less than' val.

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 5348 of file stl_algo.h.

💜 `std::merge` — the no-functor main character 💜

template<typename _InputIterator1 , typename _InputIterator2 , typename
    _OutputIterator > _OutputIterator std::merge (_InputIterator1 __first1,
    _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2
    __last2, _OutputIterator __result) [inline]

Merges two sorted ranges. Same merge slay, just without the custom comparison moment.

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 iterator pointing to the first element 'not less than' val.

Definition at line 5285 of file stl_algo.h.

🌈 `std::min` — with the comparison functor 🌈

template<typename _Tp , typename _Compare > const _Tp & std::min (const _Tp
    & __a, const _Tp & __b, _Compare __comp) [inline]

This does what you think it does. Lowkey the most reliable bestie in the algorithm friend group.

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 232 of file stl_algobase.h.

🫶 `std::min` — the simple classic 🫶

template<typename _Tp > const _Tp & std::min (const _Tp & __a, const _Tp &
    __b) [inline]

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 186 of file stl_algobase.h.

Referenced by std::tr1::__detail::__ellint_rc(), std::tr1::__detail::__ellint_rd(), std::tr1::__detail::__ellint_rf(), std::tr1::__detail::__ellint_rj(), std::tr1::__detail::__expint_En_cont_frac(), __gnu_cxx::__versa_string< _CharT, _Traits, _Alloc, _Base >::compare(), std::basic_string< _CharT, _Traits, _Alloc >::compare(), std::basic_string< char >::compare(), std::basic_stringbuf< _CharT, _Traits, _Alloc >::overflow(), __gnu_parallel::parallel_random_shuffle_drs(), std::basic_istream< _CharT, _Traits >::readsome(), std::basic_string< _CharT, _Traits, _Alloc >::rfind(), __gnu_parallel::sequential_random_shuffle(), std::basic_filebuf< _CharT, _Traits >::underflow(), std::basic_streambuf< _CharT, _Traits >::xsgetn(), and std::basic_streambuf< _CharT, _Traits >::xsputn().

🍓 `std::min_element` — minimum-finding with a functor 🍓

template<typename _ForwardIterator , typename _Compare > _ForwardIterator
    std::min_element (_ForwardIterator __first, _ForwardIterator __last,
    _Compare __comp) [inline]

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 6014 of file stl_algo.h.

Referenced by std::valarray< _Tp >::min().

🧚 `std::min_element` — the simple minimum hunt 🧚

template<typename _ForwardIterator > _ForwardIterator std::min_element
    (_ForwardIterator __first, _ForwardIterator __last) [inline]

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 5986 of file stl_algo.h.

👑 `std::minmax` — both at once, with `comp` 👑

template<typename _Tp , typename _Compare > pair< const _Tp &, const _Tp & >
    std::minmax (const _Tp & __a, const _Tp & __b, _Compare __comp) [inline]

Determines min and max at once as an ordered pair. Efficient? We love to see it.

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 3977 of file stl_algo.h.

References std::minmax().

🎀 `std::minmax` — both at once, no functor 🎀

template<typename _Tp > pair< const _Tp &, const _Tp & > std::minmax (const
    _Tp & __a, const _Tp & __b) [inline]

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 3958 of file stl_algo.h.

References std::minmax().

Referenced by std::minmax().

💫 `std::minmax_element` — with comparison functor 💫

template<typename _ForwardIterator , typename _Compare >
    pair<_ForwardIterator, _ForwardIterator> std::minmax_element
    (_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
    [inline]

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 4072 of file stl_algo.h.

🌟 `std::minmax_element` — the simple version 🌟

template<typename _ForwardIterator > pair<_ForwardIterator,
    _ForwardIterator> std::minmax_element (_ForwardIterator __first,
    _ForwardIterator __last) [inline]

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

Parameters:

first — start of range.
last — end of range.

Definition at line 3996 of file stl_algo.h.

🔥 `std::next_permutation` — with comparison functor 🔥

template<typename _BidirectionalIterator , typename _Compare > bool
    std::next_permutation (_BidirectionalIterator __first,
    _BidirectionalIterator __last, _Compare __comp) [inline]

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.

So the comp-flavoured version wraps up like this: it 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 that set, and returns true if there are more sequences to generate. If the sequence is already the largest of the set, the smallest one gets generated and false comes back at you. 🎠

Definition at line 3631 of file stl_algo.h.

References std::iter_swap(), and std::reverse().

🔁 `std::next_permutation` (no compare, no drama)

template<typename _BidirectionalIterator > bool std::next_permutation
    (_BidirectionalIterator __first, _BidirectionalIterator __last) [inline]

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. Literally it's the dictionary-order carousel and you're just stepping one seat over. ✨

Definition at line 3574 of file stl_algo.h.

References std::iter_swap(), and std::reverse().

🎯 `std::nth_element` (but make it custom-comp)

template<typename _RandomAccessIterator , typename _Compare > void
    std::nth_element (_RandomAccessIterator __first, _RandomAccessIterator
    __nth, _RandomAccessIterator __last, _Compare __comp) [inline]

Sort a sequence just enough to find a particular position using a predicate for comparison. Bestie, "just enough" is the whole vibe here. 💅

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. So it's not sorted-sorted, it's vibes-sorted. 🦋

Definition at line 5169 of file stl_algo.h.

References std::__lg().

🎯 `std::nth_element` (default compare)

template<typename _RandomAccessIterator > void std::nth_element
    (_RandomAccessIterator __first, _RandomAccessIterator __nth,
    _RandomAccessIterator __last) [inline]

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. No cap, that one element is exactly where it belongs and everything else is doing whatever. 😭

Definition at line 5130 of file stl_algo.h.

References std::__lg().

🧺 `std::partial_sort` (with your own predicate)

template<typename _RandomAccessIterator , typename _Compare > void
    std::partial_sort (_RandomAccessIterator __first, _RandomAccessIterator
    __middle, _RandomAccessIterator __last, _Compare __comp) [inline]

Sort the smallest elements of a sequence using a predicate for comparison. Only the smallest ones get the glow-up. 👑

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 5092 of file stl_algo.h.

References std::__heap_select(), and std::sort_heap().

🧺 `std::partial_sort` (default compare)

template<typename _RandomAccessIterator > void std::partial_sort
    (_RandomAccessIterator __first, _RandomAccessIterator __middle,
    _RandomAccessIterator __last) [inline]

Sort the smallest elements of a sequence. That's it, that's the whole gig. 🍓

Parameters

first — An iterator.
middle — Another iterator.
last — Another iterator.

Returns — Nothing.

Definition at line 5053 of file stl_algo.h.

References std::__heap_select(), and std::sort_heap().

📋 `std::partial_sort_copy` (with predicate)

template<typename _InputIterator , typename _RandomAccessIterator , typename
    _Compare > _RandomAccessIterator std::partial_sort_copy (_InputIterator
    __first, _InputIterator __last, _RandomAccessIterator __result_first,
    _RandomAccessIterator __result_last, _Compare __comp) [inline]

Copy the smallest elements of a sequence using a predicate for comparison. Sort and copy? She does both. 💅✨

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 2011 of file stl_algo.h.

References std::make_heap(), and std::sort_heap().

📋 `std::partial_sort_copy` (default compare)

template<typename _InputIterator , typename _RandomAccessIterator >
    _RandomAccessIterator std::partial_sort_copy (_InputIterator __first,
    _InputIterator __last, _RandomAccessIterator __result_first,
    _RandomAccessIterator __result_last) [inline]

Copy the smallest elements of a sequence. Same energy, zero functor. 🎀

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 1945 of file stl_algo.h.

References std::make_heap(), and std::sort_heap().

⏪ `std::prev_permutation` (with a comparison functor)

template<typename _BidirectionalIterator , typename _Compare > bool
    std::prev_permutation (_BidirectionalIterator __first,
    _BidirectionalIterator __last, _Compare __comp) [inline]

Permute range into the previous 'dictionary' ordering using comparison functor. Yes bestie, you can go backwards too. 🦋

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 3744 of file stl_algo.h.

References std::iter_swap(), and std::reverse().

⏪ `std::prev_permutation` (default compare)

template<typename _BidirectionalIterator > bool std::prev_permutation
    (_BidirectionalIterator __first, _BidirectionalIterator __last) [inline]

Permute range into the previous 'dictionary' ordering. Rewind the dictionary tape, no cap. 📼

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 3687 of file stl_algo.h.

References std::iter_swap(), and std::reverse().

🔥 `std::sort` (custom predicate, the icon)

template<typename _RandomAccessIterator , typename _Compare > void std::sort
    (_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare
    __comp) [inline]

Sort the elements of a sequence using a predicate for comparison. The main character of this whole manpage, honestly. 👑

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

⚠️ Heads up: the relative ordering of equivalent elements is not preserved. Use stable_sort() if you need that — this is the flaky one, she does not remember who came first. 💀

Definition at line 5243 of file stl_algo.h.

References std::__final_insertion_sort(), std::__introsort_loop(), and std::__lg().

🔥 `std::sort` (default compare)

template<typename _RandomAccessIterator > void std::sort
    (_RandomAccessIterator __first, _RandomAccessIterator __last) [inline]

Sort the elements of a sequence. Periodt. ✨

Parameters

first — An iterator.
last — Another iterator.

Returns — Nothing.

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

⚠️ Same warning, same energy: the relative ordering of equivalent elements is not preserved, use stable_sort() if this is needed. 😭

Definition at line 5207 of file stl_algo.h.

References std::__final_insertion_sort(), std::__introsort_loop(), and std::__lg().

👑 `std::stable_sort` (custom predicate, she remembers everything)

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. She's the friend who remembers your birthday and the exact order things happened in. 🎀💖

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 each iterator i in the range [first,last-1).

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(). Told you — she keeps receipts. 🧾✨

Definition at line 5449 of file stl_algo.h.

References std::__inplace_stable_sort(), std::_Temporary_buffer< _ForwardIterator, _Tp >::begin(), and std::_Temporary_buffer< _ForwardIterator, _Tp >::size().

🌸 `std::stable_sort` — the one that keeps your faves in order 🎀

template<typename _RandomAccessIterator >
    void std::stable_sort (_RandomAccessIterator __first, _RandomAccessIterator __last) [inline]

okay bestie, THIS is the moment. 💅 std::stable_sort sorts the elements of a sequence and preserves the relative order of equivalent elements. like it sorts, but it does NOT do your equivalent elements dirty. iconic behaviour, honestly.

✨ Parameters

first — an iterator. that's it. that's the descriptor. 🫶
last — another iterator.

✨ Returns

Nothing. zero. nada. it just does the thing and leaves. main character energy tbh 😌

✨ What it actually does

It sorts the elements in the range [first,last) in ascending order, such that *(i+1)<*i is false for each iterator i in the range [first,last-1). read that twice, it's literally the whole vibe check ✅.

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(). fr fr, the ties stay in the exact same order they walked in with. no chaos, no shuffling your besties around. 🧚‍♀️

ngl this is the whole reason you'd pick stable_sort over plain sort — the "stable" is not decorative, it's the entire personality 💀

✨ The receipts 📜

Definition at line 5407 of file stl_algo.h.

✨ References (the lore) 🔥

std::__inplace_stable_sort()
std::_Temporary_buffer<_ForwardIterator, _Tp>::begin()
std::_Temporary_buffer<_ForwardIterator, _Tp>::size()

✨ Author 👑

Generated automatically by Doxygen for libstdc++ from the source code. so not a human, just a little robot doing its thing 🤖💖

and that's a wrap on the page bestie!! 🎀 this one's from libstdc++, dated 21 Apr 2009, living its life as Sorting Algorithms(3) in the manual — go forth and sort stably, you absolute legend 💅✨🌈

📦 where this page comes from

nixpkgs unstable: std-man-pages 4.4.0
💖 girlified by deepseek-ai/DeepSeek-V4.1-Flash-1017 on 2026-11-04: a language model's rewrite of the original, under its terms

SORTING_ALGORITHMS(3)