// ¿Cuánto salta cada algoritmo? Anota cada lectura y escritura del arreglo, y simula con ellas una
// cache pequeña: 32 KB, líneas de 64 bytes, cada línea en un único lugar posible (correspondencia directa).
// Es un conteo sobre un modelo, no una medición de la cache de esta máquina.
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>

namespace {

class CacheModel {
public:
    CacheModel() : tags_(lines_in_cache, -1) {}

    // position es el número del int dentro de la memoria simulada.
    void touch(std::size_t position) {
        std::int64_t line = static_cast<std::int64_t>(position / ints_per_line);
        std::int64_t& tag = tags_[static_cast<std::size_t>(line) % lines_in_cache];
        accesses_++;
        if (tag != line) {
            misses_++;
            tag = line;
        }
    }
    long accesses() const { return accesses_; }
    long misses() const { return misses_; }

private:
    static constexpr std::size_t ints_per_line = 64 / sizeof(int);
    static constexpr std::size_t lines_in_cache = 32 * 1024 / 64;
    std::vector<std::int64_t> tags_;
    long accesses_ = 0;
    long misses_ = 0;
};

void sift_down(std::vector<int>& items, std::size_t i, std::size_t n, CacheModel& cache) {
    while (true) {
        std::size_t left = 2 * i + 1;
        std::size_t right = 2 * i + 2;
        std::size_t largest = i;
        cache.touch(i);
        if (left < n) {
            cache.touch(left);
            if (items[largest] < items[left]) {
                largest = left;
            }
        }
        if (right < n) {
            cache.touch(right);
            if (items[largest] < items[right]) {
                largest = right;
            }
        }
        if (largest == i) {
            return;
        }
        std::swap(items[i], items[largest]);
        i = largest;
    }
}

void modeled_heapsort(std::vector<int>& items, CacheModel& cache) {
    for (std::size_t i = items.size() / 2; i > 0; i--) {
        sift_down(items, i - 1, items.size(), cache);
    }
    for (std::size_t end = items.size(); end > 1; end--) {
        cache.touch(0);
        cache.touch(end - 1);
        std::swap(items[0], items[end - 1]);
        sift_down(items, 0, end - 1, cache);
    }
}

// Mergesort de abajo hacia arriba. El arreglo auxiliar va después del original en la memoria simulada.
void modeled_mergesort(std::vector<int>& items, CacheModel& cache) {
    const std::size_t n = items.size();
    std::vector<int> buffer(n);
    std::size_t source_at = 0;
    std::size_t target_at = n;
    for (std::size_t width = 1; width < n; width *= 2) {
        for (std::size_t low = 0; low < n; low += 2 * width) {
            std::size_t mid = std::min(low + width, n);
            std::size_t high = std::min(low + 2 * width, n);
            std::size_t a = low;
            std::size_t b = mid;
            std::size_t out = low;
            while (a < mid || b < high) {
                bool take_b;
                if (a < mid && b < high) {
                    cache.touch(source_at + a);
                    cache.touch(source_at + b);
                    take_b = items[b] < items[a];
                } else {
                    take_b = a == mid;
                    cache.touch(source_at + (take_b ? b : a));
                }
                cache.touch(target_at + out);
                buffer[out++] = take_b ? items[b++] : items[a++];
            }
        }
        items.swap(buffer);
        std::swap(source_at, target_at);
    }
}

}  // namespace

int main() {
    std::cout << "        n  algoritmo     accesos       fallos  fallos/n\n";
    for (int n : {1000, 10000, 100000, 1000000, 4000000}) {
        std::vector<int> input(n);
        std::iota(input.begin(), input.end(), 0);
        std::mt19937 generator(13);
        std::shuffle(input.begin(), input.end(), generator);

        std::vector<int> items = input;
        CacheModel heap_cache;
        modeled_heapsort(items, heap_cache);
        if (!std::is_sorted(items.begin(), items.end())) {
            return 1;
        }
        items = input;
        CacheModel merge_cache;
        modeled_mergesort(items, merge_cache);
        if (!std::is_sorted(items.begin(), items.end())) {
            return 1;
        }
        std::cout << std::fixed << std::setprecision(2);
        std::cout << std::setw(9) << n << "   heapsort" << std::setw(12) << heap_cache.accesses() << std::setw(13)
                  << heap_cache.misses() << std::setw(10) << double(heap_cache.misses()) / n << "\n";
        std::cout << std::setw(9) << n << "  mergesort" << std::setw(12) << merge_cache.accesses() << std::setw(13)
                  << merge_cache.misses() << std::setw(10) << double(merge_cache.misses()) / n << "\n";
    }
    return 0;
}