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