// Quicksort con contadores: comparaciones, profundidad y pivotes buenos.
// Trabaja sobre rangos semiabiertos [lo, hi).
#pragma once

#include <cstddef>
#include <random>
#include <utility>
#include <vector>

enum class Pivot { First, Random };

struct QuickStats {
    long long comparisons = 0;
    int max_depth = 0;           // niveles de llamadas con al menos dos elementos
    long long large_calls = 0;   // llamadas con al menos 16 elementos
    long long good_pivots = 0;   // de esas, las que dejaron al pivote en el medio
};

// El pivote va a a[lo] según la regla. % tiene un sesgo despreciable aquí, y da los mismos
// resultados en toda máquina, cosa que std::uniform_int_distribution no promete.
inline void choose_pivot(std::vector<int>& a, int lo, int hi, Pivot rule, std::mt19937& rng) {
    if (rule == Pivot::Random) {
        const auto size = static_cast<unsigned>(hi - lo);
        std::swap(a[static_cast<std::size_t>(lo)], a[static_cast<std::size_t>(lo) + rng() % size]);
    }
}

// Partición en dos: al terminar, [lo, p) < pivote ≤ [p + 1, hi).
inline void quicksort_two_way(std::vector<int>& a, int lo, int hi, Pivot rule, std::mt19937& rng,
                              QuickStats& stats, int depth = 1) {
    const int size = hi - lo;
    if (size < 2) return;
    if (depth > stats.max_depth) stats.max_depth = depth;
    choose_pivot(a, lo, hi, rule, rng);
    const int pivot = a[static_cast<std::size_t>(lo)];
    int p = lo;
    for (int i = lo + 1; i < hi; i++) {
        stats.comparisons++;
        if (a[static_cast<std::size_t>(i)] < pivot) {
            p++;
            std::swap(a[static_cast<std::size_t>(i)], a[static_cast<std::size_t>(p)]);
        }
    }
    std::swap(a[static_cast<std::size_t>(lo)], a[static_cast<std::size_t>(p)]);
    if (size >= 16) {
        // Pivote bueno: su posición final cae en la mitad central del rango.
        const int rank = p - lo;
        stats.large_calls++;
        if (size / 4 <= rank && rank < size - size / 4) stats.good_pivots++;
    }
    quicksort_two_way(a, lo, p, rule, rng, stats, depth + 1);
    quicksort_two_way(a, p + 1, hi, rule, rng, stats, depth + 1);
}

// Partición en tres: [lo, lt) < pivote, [lt, gt) = pivote, [gt, hi) > pivote.
// Los iguales al pivote ya quedan en su lugar y no vuelven a tocarse.
inline void quicksort_three_way(std::vector<int>& a, int lo, int hi, Pivot rule, std::mt19937& rng,
                                QuickStats& stats, int depth = 1) {
    if (hi - lo < 2) return;
    if (depth > stats.max_depth) stats.max_depth = depth;
    choose_pivot(a, lo, hi, rule, rng);
    const int pivot = a[static_cast<std::size_t>(lo)];
    int lt = lo;
    int gt = hi;
    int i = lo + 1;
    while (i < gt) {
        const int value = a[static_cast<std::size_t>(i)];
        stats.comparisons++;
        if (value < pivot) {
            std::swap(a[static_cast<std::size_t>(i)], a[static_cast<std::size_t>(lt)]);
            lt++;
            i++;
        } else {
            stats.comparisons++;
            if (value > pivot) {
                gt--;
                std::swap(a[static_cast<std::size_t>(i)], a[static_cast<std::size_t>(gt)]);
            } else {
                i++;
            }
        }
    }
    quicksort_three_way(a, lo, lt, rule, rng, stats, depth + 1);
    quicksort_three_way(a, gt, hi, rule, rng, stats, depth + 1);
}