.. Algorithms/Transformation Algorithms//sort |95

sort
====

Synopsis
--------

.. parsed-literal::
    
    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/end<Seq>| sorted according
to the ordering relation ``Pred``. 

|transformation algorithm disclaimer|


Header
------

.. parsed-literal::
    
    #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
--------------------

|Semantics disclaimer...| |Reversible Algorithm|.

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


.. parsed-literal::

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

:Return type:
    A type.
    
:Semantics:
    If ``size<s>::value <= 1``, equivalent to

    .. parsed-literal::

        typedef copy<s,in>::type r;
    
    
    otherwise equivalent to 
    
    .. parsed-literal::

        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
-------

.. parsed-literal::
    
    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|