// Cuenta las comparaciones de mergesort con varias entradas.
#include <iostream>
#include <numeric>
#include <random>
#include <string>
#include <vector>

#include "comparison_count.h"

static std::string pad(long long value, std::size_t width) {
    std::string text = std::to_string(value);
    return text + std::string(width > text.size() ? width - text.size() : 1, ' ');
}

int main() {
    std::mt19937 rng(2);
    std::cout << "n        ordenado  invertido al azar  peor      fórmula\n";
    for (std::size_t n : {16u, 17u, 1000u, 1024u, 65536u, 1000000u}) {
        std::vector<int> sorted(n);
        std::iota(sorted.begin(), sorted.end(), 0);
        std::vector<int> reversed(sorted.rbegin(), sorted.rend());
        std::vector<int> shuffled = sorted;
        for (std::size_t i = n - 1; i > 0; i--) {
            std::swap(shuffled[i], shuffled[rng() % (i + 1)]);
        }
        std::cout << pad(static_cast<long long>(n), 9) << pad(count_comparisons(sorted), 10)
                  << pad(count_comparisons(reversed), 10) << pad(count_comparisons(shuffled), 9)
                  << pad(count_comparisons(worst_case_input(sorted)), 10) << worst_case_formula(n) << '\n';
    }
}