// Mergesort sobre un std::vector, con un solo arreglo auxiliar para toda la recursión.
#pragma once

#include <cstddef>
#include <vector>

// Mezcla a[lo, mid) y a[mid, hi), ya ordenados, y deja ordenado a[lo, hi).
// Invariante, antes de cada vuelta: buffer[lo, k) tiene, ordenados, los elementos de a[lo, i) y
// de a[mid, j), y ninguno es mayor que algún elemento que todavía no se copió.
template <typename T>
void merge_ranges(std::vector<T>& a, std::vector<T>& buffer, std::size_t lo, std::size_t mid, std::size_t hi) {
    std::size_t i = lo;
    std::size_t j = mid;
    for (std::size_t k = lo; k < hi; k++) {
        // Con <=, en un empate pasa primero el de la izquierda: eso hace estable el orden.
        if (j == hi || (i < mid && a[i] <= a[j])) {
            buffer[k] = a[i];
            i++;
        } else {
            buffer[k] = a[j];
            j++;
        }
    }
    for (std::size_t k = lo; k < hi; k++) {
        a[k] = buffer[k];
    }
}

template <typename T>
void sort_range(std::vector<T>& a, std::vector<T>& buffer, std::size_t lo, std::size_t hi) {
    if (hi - lo <= 1) {
        return;
    }
    std::size_t mid = lo + (hi - lo) / 2;
    sort_range(a, buffer, lo, mid);
    sort_range(a, buffer, mid, hi);
    merge_ranges(a, buffer, lo, mid, hi);
}

template <typename T>
void merge_sort(std::vector<T>& a) {
    std::vector<T> buffer(a.size());
    sort_range(a, buffer, 0, a.size());
}