[alg.sorting.general]

# 26 Algorithms library [[algorithms]](./#algorithms)

## 26.8 Sorting and related operations [[alg.sorting]](alg.sorting#general)

### 26.8.1 General [alg.sorting.general]

[1](#1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8666)

The operations in [[alg.sorting]](alg.sorting "26.8 Sorting and related operations") defined directly in namespace std have two versions:
one that takes a function object of type Compare and
one that uses an operator<[.](#1.sentence-1)

[2](#2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8672)

Compare is a function object type ([[function.objects]](function.objects "22.10 Function objects"))
that meets the requirements for a template parameter
named BinaryPredicate ([[algorithms.requirements]](algorithms.requirements "26.2 Algorithms requirements"))[.](#2.sentence-1)

The return value of the function call operation
applied to an object of type Compare,
when converted to bool,
yields true if the first argument of the call is less than the second, andfalse otherwise[.](#2.sentence-2)

Compare comp is used throughout
for algorithms assuming an ordering relation[.](#2.sentence-3)

[3](#3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8685)

For all algorithms that take Compare,
there is a version that uses operator< instead[.](#3.sentence-1)

That is, comp(*i, *j) != false defaults to *i < *j != false[.](#3.sentence-2)

For algorithms other than those described in [[alg.binary.search]](alg.binary.search "26.8.4 Binary search"),comp shall induce a strict weak ordering on the values[.](#3.sentence-3)

[4](#4)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8692)

The term [*strict*](#def:strict) refers to the requirement
of an irreflexive relation (!comp(x, x) for all x),
and the term [*weak*](#def:weak) to requirements
that are not as strong as those for a total ordering,
but stronger than those for a partial ordering[.](#4.sentence-1)

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:

- [(4.1)](#4.1)

comp(a, b) && comp(b, c) implies comp(a, c)

- [(4.2)](#4.2)

equiv(a, b) && equiv(b, c) implies equiv(a, c)

[*Note [1](#note-1)*:

Under these conditions, it can be shown that

- [(4.3)](#4.3)

equiv is an equivalence relation,

- [(4.4)](#4.4)

comp induces a well-defined relation
 on the equivalence classes determined by equiv, and

- [(4.5)](#4.5)

the induced relation is a strict total ordering[.](#4.sentence-2)

â *end note*]

[5](#5)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8718)

A sequence is [*sorted with respect to a comp and proj*](#def:sorted_with_respect_to_a_comp_and_proj) for a comparator and projection comp and proj 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,bool(invoke(comp, invoke(proj, *(i + n)), invoke(proj, *i))) is false[.](#5.sentence-1)

[6](#6)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8731)

A sequence is [*sorted with respect to a comparator comp*](#def:sorted_with_respect_to_a_comparator_comp) for a comparator comp if it is sorted with respect tocomp and identity{} (the identity projection)[.](#6.sentence-1)

[7](#7)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8738)

A sequence [start, finish) is[*partitioned with respect to an expression*](#def: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[.](#7.sentence-1)

[8](#8)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8745)

In the descriptions of the functions that deal with ordering relationships
we frequently use a notion of equivalence to describe concepts
such as stability[.](#8.sentence-1)

The equivalence to which we refer is not necessarily an operator==,
but an equivalence relation induced by the strict weak ordering[.](#8.sentence-2)

That is, two elements a and b are considered equivalent
if and only if !(a < b) && !(b < a)[.](#8.sentence-3)
