#include <vector>
#include <iostream>
#include <iterator>
#include <functional>

template<typename Iter>
using iter_vt = typename std::iterator_traits<Iter>::value_type;

template<typename Iter, typename Comp>
iter_vt<Iter> pivot(Iter begin, Iter end, Comp cmp){
    auto mid = (begin + end) / 2;
    auto lst = end - 1;

    if (cmp(*mid,*begin)) {
        std::swap(*begin, *mid);
    }
    if (cmp(*mid,*lst)) {
        std::swap(*mid, *lst);
    }
    if (cmp(*lst,*begin)){
        std::swap(*begin, *lst);
    }

    return *lst;
}

template<typename Iter, typename Comp>
Iter qsort_partition(Iter beg, Iter end, Comp cmp){
    iter_vt<Iter> pivot = qsort_pivot(beg, end, cmp);

    Iter pos = beg;
    for(; beg != end-1; ++beg){
        if(cmp(*beg, pivot)){
            std::swap(*pos, *beg);
            ++pos;
        }
    }
    std::swap(*pos, *(end-1));

    return pos;
}

template<typename Iter, typename Comp = std::less<iter_vt<Iter>>>
void Sort(Iter beg, Iter end, Comp cmp = std::less<iter_vt<Iter>>{}){
    if(std::distance(beg,end) < 2)
        return;

    Iter mid = qsort_partition(beg,end,cmp);

    Sort(beg  , mid, cmp);
    Sort(mid+1, end, cmp);
}

template<typename T, typename Comp = std::less<T>>
void Sort(std::vector<T>* pv, Comp cmp = std::less<T>{}){
    Sort(pv->begin(), pv->end(), cmp);
}