// El árbol de llamadas de mergesort para n = 8: primero las divisiones, después las mezclas.
#include <cstddef>
#include <iostream>
#include <string>
#include <vector>

namespace {

struct Level {
    std::string runs;
    long long comparisons = 0;
    long long copied = 0;
};

std::string show(const std::vector<int>& items, std::size_t lo, std::size_t hi) {
    std::string text = "[";
    for (std::size_t i = lo; i < hi; i++) {
        text += (i == lo ? "" : " ") + std::to_string(items[i]);
    }
    return text + "] ";
}

void sort_range(std::vector<int>& items, std::size_t lo, std::size_t hi, std::size_t depth,
                std::vector<Level>& down, std::vector<Level>& up) {
    if (down.size() <= depth) {
        down.resize(depth + 1);
        up.resize(depth + 1);
    }
    down[depth].runs += show(items, lo, hi);
    if (hi - lo < 2) {
        return;
    }
    std::size_t mid = lo + (hi - lo) / 2;
    sort_range(items, lo, mid, depth + 1, down, up);
    sort_range(items, mid, hi, depth + 1, down, up);

    std::vector<int> merged;
    std::size_t left = lo;
    std::size_t right = mid;
    while (left < mid && right < hi) {
        up[depth].comparisons++;
        merged.push_back(items[right] < items[left] ? items[right++] : items[left++]);
    }
    while (left < mid) {
        merged.push_back(items[left++]);
    }
    while (right < hi) {
        merged.push_back(items[right++]);
    }
    for (std::size_t i = lo; i < hi; i++) {
        items[i] = merged[i - lo];
        up[depth].copied++;
    }
    up[depth].runs += show(items, lo, hi);
}

}  // namespace

int main() {
    std::vector<int> items = {5, 2, 8, 1, 9, 3, 7, 4};
    std::vector<Level> down;
    std::vector<Level> up;
    sort_range(items, 0, items.size(), 0, down, up);

    std::cout << "dividir\n";
    for (std::size_t depth = 0; depth < down.size(); depth++) {
        std::cout << "  nivel " << depth << ": " << down[depth].runs << "\n";
    }
    std::cout << "mezclar\n";
    for (std::size_t depth = up.size() - 1; depth-- > 0;) {
        std::cout << "  nivel " << depth << ": " << up[depth].runs << "\n";
        std::cout << "           " << up[depth].comparisons << " comparaciones, "
                  << up[depth].copied << " elementos copiados\n";
    }
    return 0;
}