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

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


// quick ソートのサブルーチンのためのnamespace. 他は直接よびださないこと.
namespace quick_sort_detail {

// 挿入ソート.
// Tが大きいとスタックにコピー(m)を作ることになるので、 再帰中のスタックを消費しないように関数分離.
// (ループあるし単純すぎるわけでないのでTが大きいときに inlineされることはないだろうと期待)
template<typename BidiIte, class CMP>
void quick_sort_insertion_sort_(BidiIte first, BidiIte last, CMP cmp)
{
    typedef typename std::iterator_traits<BidiIte>::value_type T;
    BidiIte i = first;
    while (++i != last) {
        T       tmp( *i );
        BidiIte j = i;
        BidiIte k = i;
        do {
            --k;
            if (!cmp(tmp, *k))
                break;
            *j = *k;
            --j;
        } while (k != first);
        *j = tmp;
    }
}


// quickソートのループ部分
// Tが大きいとスタックにコピー(m)を作ることになるので、 再帰中のスタックを消費しないように関数分離.
// (ループあるし単純すぎるわけでないのでTが大きいときに inlineされることはないだろうと期待)
template<typename BidiIte, class CMP>
BidiIte  quick_sort_loop_(BidiIte first, BidiIte last, CMP cmp, std::size_t size) {
    typedef typename std::iterator_traits<BidiIte>::value_type T;
    using       std::iter_swap;
    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;
    }
    return l;
}

}


template<typename BidiIte, class C>
void quick_sort(BidiIte first, BidiIte last, C cmp)
{
    std::size_t size = std::size_t(std::distance(first, last));
    if (size <= 32) {
        if (size > 1)
            quick_sort_detail::quick_sort_insertion_sort_(first, last, cmp);
        return;
    }

    BidiIte     mid = quick_sort_detail::quick_sort_loop_(first, last, cmp, size);
    quick_sort(first, mid , cmp);
    quick_sort(mid  , 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