#include <vector>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <random>
#include <chrono>
#include <limits>

class muTimer
{
    using Clock = std::chrono::high_resolution_clock;
    bool active = false;
    Clock::duration   duration_;
    Clock::time_point start_ = Clock::now(), stop_ = Clock::now();

    muTimer(const muTimer&)             = delete;
    muTimer& operator=(const muTimer&)  = delete;
public:
    using ns       = std::chrono::nanoseconds;
    using mks      = std::chrono::microseconds;
    using ms       = std::chrono::milliseconds;
    muTimer() { reset(); start(); }
    ~muTimer() = default;
    muTimer& reset()
    {
        duration_ = std::chrono::nanoseconds(0);
        active    = false;
        return *this;
    }
    muTimer& start()
    {
        if (!active)
        {
            start_ = Clock::now();
            active = true;
        }
        return *this;
    }
    muTimer& stop()
    {
        if (active)
        {
            stop_      = Clock::now();
            duration_ += stop_ - start_;
            active     = false;
        }
        return *this;
    }
    template<typename T = mks>
        unsigned long long duration()
    {
        return static_cast<unsigned long long>
            (std::chrono::duration_cast<T>(stop_-start_).count());
    }
};

using namespace std;


// BubbleSort
template<typename Iter>
void BubbleSort(Iter b, Iter e)
{
    --e;
    for(; b != e; ++b)
        for(Iter k = e, j = k--; j != b; j = k--)
            if (*j < *k) swap(*j,*k);
}

// EBubbleSort
template<typename Iter>
void EBubbleSort(Iter b, Iter e)
{
    --e;
    for(; b != e; ++b)
    {
        Iter last = e;
        for(Iter k = e, j = k--; j != b; j = k--)
            if (*j < *k)
            {
                swap(*j,*k);
                last = k;
            }
        if (last == e) break; else b = last;
    }
}

template<typename Iter>
void InsertionSort(Iter b, Iter e)
{
    typedef typename iterator_traits<Iter>::value_type Value;
    Iter i = b;
    for(++i; i != e; ++i)
    {
        Value x = *i;
        Iter j = i, k = i;
        for(--j; (k != b) && (x < *j); --j, --k) *k = *j;
        *k = x;
    }
}

template<typename Iter>
void SelectionSort(Iter b, Iter e)
{
    for(; b!= e; ++b)
    {
        Iter mini = b, i = b;
        for(++i; i != e; ++i)
            if (*i < *mini) mini = i;
        if (b != mini) swap(*b,*mini);
    }
}



using matrix = vector<vector<int>>;

int main(int argc, char * argv[])
{
    random_device rd;  
    mt19937 gen(rd()); 
    uniform_int_distribution<> dis(numeric_limits<int>::min(), numeric_limits<int>::max());
    const int EXPS = 100000;

    for(int N = 4; N <= 32; N *= 2)
    {
        // ‡ Ї®«­пҐ¬
        matrix m;
        for(int i = 0; i < EXPS; ++i)
        {
            vector<int> v;
            for(int j = 0; j < N; ++j) v.push_back(dis(gen));
            m.push_back(v);
        }
        {
            matrix s = m;
            muTimer mt;
            for(auto& v: s) sort(v.begin(),v.end());
            mt.stop();
            long long sum = 0;
            for(const auto& v: m)
                for(auto i: v) sum += i;
            cout << "stl sort    : N = " << setw(2) << N << " : " <<
                sum << " for " << setw(6) << mt.duration<>() << " mks\n";
        }
        {
            matrix s = m;
            muTimer mt;
            for(auto& v: s) stable_sort(v.begin(),v.end());
            mt.stop();
            long long sum = 0;
            for(const auto& v: m)
                for(auto i: v) sum += i;
            cout << "stable sort : N = " << setw(2) << N << " : " <<
                sum << " for " << setw(6) << mt.duration<>() << " mks\n";
        }
        {
            matrix s = m;
            muTimer mt;
            for(auto& v: s) BubbleSort(v.begin(),v.end());
            mt.stop();
            long long sum = 0;
            for(const auto& v: m)
                for(auto i: v) sum += i;
            cout << "Bubble sort : N = " << setw(2) << N << " : " <<
                sum << " for " << setw(6) << mt.duration<>() << " mks\n";
        }
        {
            matrix s = m;
            muTimer mt;
            for(auto& v: s) EBubbleSort(v.begin(),v.end());
            mt.stop();
            long long sum = 0;
            for(const auto& v: m)
                for(auto i: v) sum += i;
            cout << "EBubble sort: N = " << setw(2) << N << " : " <<
                sum << " for " << setw(6) << mt.duration<>() << " mks\n";
        }
        {
            matrix s = m;
            muTimer mt;
            for(auto& v: s) InsertionSort(v.begin(),v.end());
            mt.stop();
            long long sum = 0;
            for(const auto& v: m)
                for(auto i: v) sum += i;
            cout << "Insert sort : N = " << setw(2) << N << " : " <<
                sum << " for " << setw(6) << mt.duration<>() << " mks\n";
        }
        {
            matrix s = m;
            muTimer mt;
            for(auto& v: s) SelectionSort(v.begin(),v.end());
            mt.stop();
            long long sum = 0;
            for(const auto& v: m)
                for(auto i: v) sum += i;
            cout << "Select sort : N = " << setw(2) << N << " : " <<
                sum << " for " << setw(6) << mt.duration<>() << " mks\n";
        }

        cout << "\n\n";
    }
}