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:

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;

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<_,_> > ));