/** クィックソート
 */
#ifndef QUICK_SORT_H
#define QUICK_SORT_H

#include <cstddef>
#include <algorithm>
#include <functional>
#include <iterator>


template<typename BidiIte, class C>
void quick_sort(BidiIte first, BidiIte last, C cmp)
{
    typedef typename std::iterator_traits<BidiIte>::value_type  T;

    using std::iter_swap;
    std::size_t size = std::size_t(std::distance(first, last));
    if (size <= 32) {
        if (size <= 1)
            return;
        BidiIte i = first;
        while (++i != last) {
            const T tmp( *i );
            BidiIte j = i;
            BidiIte k = i;
            do {
                --k;
                if (!cmp(tmp, *k))
                    break;
                *j = *k;
                --j;
            } while (k != first);
            *j = tmp;
        }
        return;
    }
    BidiIte ite( first );
    std::advance( ite, size / 2 );
    const T m( *ite );
    BidiIte     l = first;
    BidiIte     r = last;
    std::size_t lc = 0;
    std::size_t rc = size;
    for (;;) {
        while (cmp(*l, m))
            ++l, ++lc;
        do {
            --r, --rc;
        } while (cmp(m, *r));
        if (lc >= rc)
            break;
        iter_swap(l, r);
        ++l, ++lc;
    }
    quick_sort(first, l   , cmp);
    quick_sort(l    , last, cmp);
}



template<typename BidiIte> inline
void quick_sort(BidiIte first, BidiIte last) {
    quick_sort( first, last, std::less<typename std::iterator_traits<BidiIte>::value_type>() );
}


#endif  // QUICK_SORT_H