#define UNIT r6_sort
#include <vector>
#include <list>
#include <cassert>

int *partition( int *low, const int *high, int pivot )
{
    while ( *low < pivot ) /* the pivot must be in there */
        ++ low;

    int *p_ptr = low;

    /* shuffle anything < pivot to the front while remembering where
     * (in the second half) we stashed the pivot itself */

    for ( int *p = low + 1; p < high; ++p )
    {
        if ( *p < pivot )
            std::swap( *low++, *p );
        if ( *p == pivot )
            p_ptr = p;
    }

    /* put the pivot in its place between the partitions */

    std::swap( *p_ptr, *low );

    return low;
}

void quicksort( int *low, int *high )
{
    if ( high - low <= 1 )
        return;

    int pivot = *low; /* whatever */
    int *p_ptr = partition( low, high, pivot );
    quicksort( low, p_ptr );
    quicksort( p_ptr + 1, high );
}

void sort( std::vector< int > &vec )
{
    quicksort( &*vec.begin(), &*vec.end() );
}

void sort( std::list< int > &list )
{
    if ( std::size( list ) <= 1 )
        return;

    std::list< int > half;

    half.splice( half.begin(), list,
                 list.begin(),
                 std::next( list.begin(), list.size() / 2 ) );

    sort( half );
    sort( list );
    list.merge( half );
}

#include "test_main.cpp"