Front Page / Algorithms / Transformation Algorithms / sort

# sort

### Synopsis

    template<
          typename Seq
        , typename Pred = less<_1,_2>
        , typename In = unspecified
        >
    struct sort
    {
        typedef unspecified type;
    };

### Description

Returns a new sequence of all elements in the range [`begin<Seq>::type`, `end<Seq>::type`) sorted according to the ordering relation `Pred`.

[Note: This wording applies to a no-inserter version(s) of the algorithm. See the Expression semantics subsection for a precise specification of the algorithm's details in all cases — end note]

### Header

    #include <boost/mpl/sort.hpp>

### Model of

Reversible Algorithm

### Parameters

Parameter | Requirement | Description
--- | --- | ---
`Seq` | Forward Sequence | An original sequence.
`Pred` | Binary Lambda Expression | An ordering relation.
`In` | Inserter | An inserter.

### Expression semantics

The semantics of an expression are defined only where they differ from, or are not defined in Reversible Algorithm.

For any Forward Sequence `s`, a binary Lambda Expression `pred`, and an Inserter `in`:

    typedef sort<s,pred,in>::type r;

Return type: | A type.

Semantics:

If `size<s>::value <= 1`, equivalent to

    typedef copy<s,in>::type r;

otherwise equivalent to

    typedef back_inserter< vector<> > aux_in;
    typedef lambda<pred>::type p;

    typedef begin<s>::type pivot;
    typedef partition<
          iterator_range< next<pivot>::type, end<s>::type >
        , apply_wrap2<p,_1,deref<pivot>::type>
        , aux_in
        , aux_in
        >::type partitioned;

    typedef sort<partitioned::first,p,aux_in >::type part1;
    typedef sort<partitioned::second,p,aux_in >::type part2;

    typedef copy<
          joint_view<
              joint_view<part1,single_view< deref<pivot>::type > >
            , part2
            >
        , in
        >::type r;

### Complexity

Average O(n log(n)) where n == `size<s>::value`, quadratic at worst.

### Example

    typedef vector_c<int,3,4,0,-5,8,-1,7> numbers;
    typedef vector_c<int,-5,-1,0,3,4,7,8> expected;
    typedef sort<numbers>::type result;

    BOOST_MPL_ASSERT(( equal< result, expected, equal_to<_,_> > ));

### See also

Transformation Algorithms, Reversible Algorithm, `partition`