// Cuenta las comparaciones entre elementos que hace mergesort.
#pragma once

#include <bit>
#include <cstddef>
#include <vector>

inline void counting_sort_range(std::vector<int>& a, std::vector<int>& buffer, std::size_t lo, std::size_t hi,
                                long long& comparisons) {
    if (hi - lo <= 1) {
        return;
    }
    std::size_t mid = lo + (hi - lo) / 2;
    counting_sort_range(a, buffer, lo, mid, comparisons);
    counting_sort_range(a, buffer, mid, hi, comparisons);
    std::size_t i = lo;
    std::size_t j = mid;
    for (std::size_t k = lo; k < hi; k++) {
        bool take_left;
        if (j == hi) {
            take_left = true;
        } else if (i == mid) {
            take_left = false;
        } else {
            comparisons++;
            take_left = a[i] <= a[j];
        }
        buffer[k] = take_left ? a[i++] : a[j++];
    }
    for (std::size_t k = lo; k < hi; k++) {
        a[k] = buffer[k];
    }
}

// Ordena una copia de a y devuelve cuántas comparaciones hizo.
inline long long count_comparisons(std::vector<int> a) {
    std::vector<int> buffer(a.size());
    long long comparisons = 0;
    counting_sort_range(a, buffer, 0, a.size(), comparisons);
    return comparisons;
}

// La recurrencia del peor caso: C(1) = 0 y C(n) = C(piso(n/2)) + C(techo(n/2)) + n - 1.
inline long long worst_case_recurrence(std::size_t n) {
    if (n <= 1) {
        return 0;
    }
    return worst_case_recurrence(n / 2) + worst_case_recurrence(n - n / 2) + static_cast<long long>(n) - 1;
}

// Su forma cerrada, con L = techo(log n): C(n) = n L - 2^L + 1.
inline long long worst_case_formula(std::size_t n) {
    std::size_t power = std::bit_ceil(n);
    long long ceil_log = std::countr_zero(power);
    return static_cast<long long>(n) * ceil_log - static_cast<long long>(power) + 1;
}

// Una entrada que obliga a n - 1 comparaciones en cada mezcla. Se reparte el resultado ordenado
// de forma alternada, para que la mezcla saque un elemento de cada lado hasta el final.
inline std::vector<int> worst_case_input(const std::vector<int>& sorted) {
    if (sorted.size() <= 1) {
        return sorted;
    }
    std::vector<int> left;
    std::vector<int> right;
    for (std::size_t i = 0; i < sorted.size(); i++) {
        // La mitad derecha tiene techo(n/2) elementos: se queda con las posiciones pares.
        (i % 2 == 0 ? right : left).push_back(sorted[i]);
    }
    std::vector<int> result = worst_case_input(left);
    std::vector<int> tail = worst_case_input(right);
    result.insert(result.end(), tail.begin(), tail.end());
    return result;
}