// Mide mergesort con n y 2n, con datos al azar. Se compila con -O2 y sin sanitizers.
// Cada fila es el menor de 3 tiempos. Los tiempos dependen de la máquina.
#include <chrono>
#include <cstddef>
#include <iomanip>
#include <iostream>
#include <random>
#include <vector>

#include "merge_sort.h"

static double measure_ms(const std::vector<int>& input) {
    double best = 1e18;
    for (int run = 0; run < 3; run++) {
        std::vector<int> a = input;
        auto start = std::chrono::steady_clock::now();
        merge_sort(a);
        auto end = std::chrono::steady_clock::now();
        best = std::min(best, std::chrono::duration<double, std::milli>(end - start).count());
    }
    return best;
}

int main() {
    std::mt19937 rng(2);
    std::cout << "n         tiempo ms  razón  predice 2(k+1)/k\n" << std::fixed;
    double previous = 0;
    for (int k = 17; k <= 23; k++) {
        std::size_t n = std::size_t{1} << k;
        std::vector<int> input(n);
        for (int& x : input) {
            x = static_cast<int>(rng() >> 1);
        }
        double ms = measure_ms(input);
        std::cout << std::left << std::setw(10) << n << std::right << std::setw(9) << std::setprecision(1) << ms;
        if (previous > 0) {
            std::cout << std::setw(7) << std::setprecision(2) << ms / previous << std::setw(9)
                      << 2.0 * k / (k - 1);
        }
        std::cout << '\n';
        previous = ms;
    }
}