#include <chrono>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <string>

using std::vector;
using std::cin;
using std::cout;
using std::chrono::steady_clock;
using std::map;
using std::string;

using TElement = int;

using test_set = map<string, vector<int>>;

template<class T1>inline std::ostream& operator<< (std::ostream& s, const std::vector<T1> container) {
	for (typename std::vector<T1>::const_iterator i = container.begin(); i != container.end(); i++) s << *i << " ";
	return s;
}

unsigned long long int get_random() {
    constexpr unsigned long long int a = 12005053;
    constexpr unsigned long long int b = 123456789;
    constexpr unsigned long long int m = 1000000007;
    static unsigned long long int x = 0;
    x = (a * x + b) % m;
    return x;
}

test_set get_tests(size_t size) {
    test_set result;
    result["sorted"].resize(size);
    std::iota(result["sorted"].begin(), result["sorted"].end(), 0);
    result["reversed"] = result["sorted"];
    std::reverse(result["reversed"].begin(), result["reversed"].end());
    result["random"].resize(size);
    std::generate(result["random"].begin(), result["random"].end(), get_random);
    return result;
}

const size_t N = 10000000;
const size_t M = 100000;
/*const size_t N = 20;
const size_t M = 5;*/

static_assert(!(N % M), "N % M != 0");

vector<TElement> with_heap(vector<TElement>& a) {
    vector<TElement> heap(a.begin(), a.begin() + M);
    std::make_heap(heap.begin(), heap.end());
    heap.resize(heap.size() + 1);
    for (auto i = a.begin() + M; i != a.end(); ++i) {
        heap.back() = *i;
        std::push_heap(heap.begin(), heap.end());
        std::pop_heap(heap.begin(), heap.end());
    }
    heap.pop_back();
    return heap;
}

vector<TElement> with_merge(vector<TElement>& a) {
    for (auto i = a.begin(); i != a.end(); i += M) {
        std::sort(i, i + M);
    }
    vector<TElement> result(a.begin(), a.begin() + M);
    vector<TElement> tmp(M);
    for (auto i = a.begin() + M; i != a.end(); i += M) {
        auto a = i;
        auto b = result.begin();
        for (auto j = tmp.begin(); j != tmp.end(); ++j) {
            if (*a < *b) {
                *j = *a;
                ++a;
            }
            else {
                *j = *b;
                ++b;
            }
        }
        result.swap(tmp);
    }
    return result;
}

template<class T> void partition_order_stat(T first, T last, size_t stat) {
    auto element = *(first + get_random() % (last - first));
    auto p = std::partition(first, last, std::bind(std::less<decltype(*first)>(), std::placeholders::_1, element));
    if (p > first + stat) {
        return partition_order_stat(first, p, stat);
    }
    if (p < first + stat) {
        return partition_order_stat(p, last, stat - (p - first));
    }
}

vector<TElement> with_random(vector<TElement>& a) {
    partition_order_stat(a.begin(), a.end(), M);
    return vector<TElement>(a.begin(), a.begin() + M);
}

int main(int, char *argv[]) {
    map<string, std::function<vector<TElement>(vector<TElement>&)>> methods;
    methods["heap"] = with_heap;
    methods["merge"] = with_merge;
    methods["random"] = with_random;

    auto method = methods[argv[1]];
    auto size = N;
    for (const auto& test : get_tests(size)) {
        int times = 0;
        double time = 0;
        while (time < .3) {
            ++times;
            auto data = test.second;
            //std::cout << data << std::endl;
            steady_clock::time_point start = steady_clock::now();
            auto answer = method(data);
            //std::cout << answer << std::endl;
            time += std::chrono::duration_cast<std::chrono::duration<double>>(steady_clock::now() - start).count();
            break;
        }
        std::cout << argv[1] << ' ' << test.first << ' ' << size << "; seconds per iteration: " << (time / times) << std::endl;
    }
    std::cout << std::endl;
    return 0;
}