These functions are found in the #include <algorithm> library. In this document, let T represent any type name.

Given a container where the entries can be reordered, it is possible to sort the entries assuming that the entries can be compared; that is, given entries $x$ and $y$, either $x < y$, $x = y$ or $x > y$. If the objects cannot be compared, or if you want a different ordering, you can pass a comparison bool comp( T lhs, T rhs ) that returns true if the first argument is less than the second, and false otherwise. This needs only be a weak ordering, meaning that there may be many items that are considered equal.

The comparison function can be, for example, the name of a function (an identifier), an object that has a public bool Class_name::operator()( T lhs, T rhs ) member operator, or a lambda expression []( T lhs, T rhs )->bool { /* some code returning a bool... */ }.

1. Sorting-related functions

void std::sort( itr_t itr_first, itr_t itr_last )
void std::sort( itr_t itr_first, itr_t itr_last, bool predicate( T lhs, T rhs ) )

Given any range defined by two iterators, the function call std::sort( itr_first, itr_last ) will sort the entries on that range. By default, items are compared using <. If you wish to provide an alternate comparison function, it should be the third argument.

    std::vector<int> v{ 5, 3, 2, 6, 5 };

    // Sort the entries so that they are in order
    std::sort( v.begin(), v.end() );

    // Sort the entries in reverse order
    std::sort( v.begin(), v.end(), []( int m, int n )->bool {
      return m > n;
    } );

Note that if it would be inefficient to have std::sort(...) sorting a container because iterators are inefficient, that container will have a sort(...) member function. You may recall that std::forward_list has such a member function.

bool std::is_sorted( itr_t itr_first, itr_t itr_last )
bool std::is_sorted( itr_t itr_first, itr_t itr_last, bool predicate( T lhs, T rhs ) )

The function std::is_sorted( itr_first, itr_last ) returns true if the range defined by the two iterators is sorted, and false otherwise.

    std::vector<int> v{ 5, 3, 2, 6, 5 };

    // This should print '0' for 'false'
    std::cout << "Is 'v' sorted? " << std::is_sorted( v.begin(), v.end() );

    // Sort the entries so that they are in order
    std::sort( v.begin(), v.end() );

    // This should print '1' for 'true'
    std::cout << "Is 'v' sorted? " << std::is_sorted( v.begin(), v.end() );

As with std::sort(...), you can pass another argument that is a function that returns true if the first argument is less than the second, and false otherwise.

itr_t std::is_sorted_until( itr_t itr_first, itr_t itr_last )
itr_t std::is_sorted_until( itr_t itr_first, itr_t itr_last, bool predicate( T lhs, T rhs ) )

This is similar to is_sorted(...), only now an iterator is returned. If the range is sorted, it returns itr_last, and if it is not sorted, there must be a first entry that is out of order, and an iterator referring to that entry is returned.

    std::vector<int> v{ 5, 3, 2, 6, 5 };

    // Also possible with #include 
    //    auto itr{ std::is_sorted_until( v.begin(), v.end(), std::greater<int<() ) };
    auto itr{ std::is_sorted_until(
      v.begin(), v.end(), []( int m, int n )->bool {
        return m > n;
      }
    ) };

    if ( itr == v.end() ) {
      std::cout << "The vector is sorted..." << std::endl;
    } else {
      std::cout << "The first entry not sorted is "
                << *itr << std::endl;
    }

void std::stable_sort( itr_t itr_first, itr_t itr_last )
void std::stable_sort( itr_t itr_first, itr_t itr_last, bool predicate( T lhs, T rhs ) )

This does not affect the sorting of integers or floating-point numbers, but in some cases, a container may have different items that are considered equal with respect to a sorting. For example, suppose we have eight objects that represent eight people:

    // Assume the 'person' class has a member
    // function that returns the age.
    person anna_lisa{ ... };  // Age 13
    person douglas{ ... };    // Age 12
    person linda{ ... };      // Age 13
    person marie{ ... };      // Age  9
    person paul{ ... };       // Age 12
    person ryan{ ... };       // Age  9
    person susan{ ... };      // Age 12
    person sylvia{ ... };     // Age 10

    vector names{ anna_lisa, douglas, linda, marie, paul, ryan, susan, sylvia };

These names were entered into the vector in alphabetical order. We can sort these objects as follows:

    // Sort these persons by their ages
    std::sort( names.begin(), names.end(), [](
      person const &a, person const &b
    )->bool {
      return a.age() < b.age()
    } );

Items that are "equal" can appear in any order, so std::sort may return any of these:

    marie, ryan, sylvia, paul, susan, douglas, anna_lisa, linda
    ryan, marie, sylvia, susan, douglas, paul, anna_lisa, linda
    marie, ryan, sylvia, douglas, susan, paul, linda, anna_lisa

A "stable" sort ensures that objects that are "equal" (in this case, the same age) will appear in the same order as they appeared in the original list. Thus, the only stable sort of the above eight persons is:

    marie, ryan, sylvia, douglas, paul, susan, anna_lisa, linda

A stable sorting algorithm is generally slower than a general sorting algorithm.

void std::partial_sort( itr_t itr_first, itr_t itr_last_sorted, itr_t itr_last )
void std::partial_sort( itr_t itr_first, itr_t itr_last_sorted, itr_t itr_last, bool predicate( T lhs, T rhs ) )

A partial sort of the range itr_first to itr_last ensures that the entries on the range itr_first to itr_last_sorted are sorted and that all entries on the subsequent range itr_last_sorted to itr_last are greater than or equal to any of the sorted entries. The order of the unsorted range may vary drastically from how they appeared in the original array; for example,

    std::vector<int> v{
       34, 15, 65, 44, 68, 42, 40, 80, 59, 65,
       23, 46, 57,  3, 29, 22, 44, 73, 99,  2
    };

    // Sort the first ten entries
    std::partial_sort(
      v.begin(), v.begin() + 10, v.end()
    );

The result when I execute this appears in the second line:

      34 15 65 44 68 42 40 80 59 65|23 46 57  3 29 22 44 73 99  2
                                   |
       2  3 15 22 23 29 34 40 42 44|80 68 65 65 59 57 46 73 99 44 
                                   |
       2  3 15 22 23 29 34 40 42 44|44 46 57 59 65 65 68 73 80 99

The original list is entirely unsorted, while the sorted list appears third. The second has the first ten entries sorted, and all subsequent entries are greater than or equal to 44 but unsorted: indeed, the second $44$ appears at the end of the unsorted range.

void std::partial_sort_copy( itr_t itr_first, itr_t itr_last, itr_t copy_first, itr_t copy_last )
void std::partial_sort_copy( itr_t itr_first, itr_t itr_last, itr_t copy_first, itr_t copy_last, bool predicate( T lhs, T rhs ) )

This is similar to a partial sort, but copies the sorted list into the range defined by the two iterators copy_first and copy_last. If this second range fewer entries, then as many entries as there are are copied over from the original range but sorted. If there are as many entries or more in the second range, all entries are copied from the first range to the second, but sorted.

void std::nth_element( itr_t itr_first, itr_t itr_to_nth, itr_t itr_last )
void std::nth_element( itr_t itr_first, itr_t itr_to_nth, itr_t itr_last, bool predicate( T lhs, T rhs ) )

The iterator itr_to_nth must refer to an item in the range described by itr_first and itr_last, and thus cannot be equal to itr_last. When this function returns, whatever value is stored at this location in the container will that item that would be there if the container was fully sorted. Everything before that point will be less than or equal to that item, and everything after that point will be greater than or equal to that item, but there is no guarantee that any other entries will be in their correct location.

This is an efficient way of finding the median of a container.

2. A possible implementation

The is_sorted(...) and is_sorted_until(...) functions simply walk through the range until either an entry is found that is out of order or we get to the end of the range. The sorting algorithm is generally an implementation of "quick sort", which is generally $O(n \ln(n))$, but can under very specific pathological cases, run in $O(n^2)$ time. Thus, if quick sort is not finishing quickly enough, the algorithm switches to a "heap sort", which also runs in $O(n \ln(n))$ time, but slower than quick sort. A stable sort includes the index in a lexicographical sort (please read the section on permutations) with the index:

    anna_lisa, douglas,   linda,     marie,     paul,      ryan,      susan,     sylvia
    0          1          2          3          4          5          6          7

anna_lisa is older than douglas, but anna_lisa is the same age as linda so we look at the index: (anna_lisa, 0) comes before (linda, 2) because the index of anna_lisa is less than the index of linda, we ensure that anna_lisa comes before linda in the subsequent stable sort.

You can view examples at replit.com.