#define UNIT r5_qsort
#include <vector>
#include <cassert>

int partition( std::vector< int > &vec, int low, int high, int pivot )
{
    while ( vec[ low ] < pivot ) /* the pivot must be in there */
        ++ low;

    int p_index = low;

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

    for ( int i = low + 1; i < high; ++i )
    {
        if ( vec[ i ] < pivot )
            std::swap( vec[ low++ ], vec[ i ] );
        if ( vec[ i ] == pivot )
            p_index = i;
    }

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

    std::swap( vec[ p_index ], vec[ low ] );

    return low;
}

void quicksort_range( std::vector< int > &vec, int low, int high )
{
    if ( high - low <= 1 )
        return;

    int pivot = vec[ low ]; /* whatever */
    int p_index = partition( vec, low, high, pivot );
    quicksort_range( vec, low, p_index );
    quicksort_range( vec, p_index + 1, high );
}

void quicksort( std::vector< int > &vec )
{
    quicksort_range( vec, 0, vec.size() );
}

#include "test_main.cpp"