// Sesión 1: sus ordenamientos. Las pruebas están en lab/tests/lab_tests.cpp.
#ifndef SORTS_H
#define SORTS_H

#include <cstddef>
#include <vector>

#include "not_implemented.h"

// Ordena items según less, de modo que nunca quede less(items[i + 1], items[i]).
// less(a, b) dice si a va antes que b, y es un orden estricto, como el < de los enteros.
//
// Debe ser estable: los elementos equivalentes conservan su orden original.
// Debe mover y no copiar: T puede no tener constructor por defecto ni ser barato de copiar.
// Hagan el buffer con reserve y push_back, y usen std::move.
// Pueden escribir las funciones auxiliares que quieran.
template <typename T, typename Less>
void merge_sort(std::vector<T>& items, Less less) {
    (void)items;
    (void)less;
    not_implemented("merge_sort");
}

// Quicksort con pivote al azar y partición en tres: menores, equivalentes y mayores que el
// pivote. Con todos los elementos iguales debe hacer una sola pasada.
//
// Usen std::mt19937 con esta semilla. Se permite copiar el pivote, y ningún otro elemento.
template <typename T, typename Less>
void quick_sort(std::vector<T>& items, Less less, unsigned seed = 2026) {
    (void)items;
    (void)less;
    (void)seed;
    not_implemented("quick_sort");
}

// Una entrada de n enteros que haga que quick_sort_first (fixed_pivot.h) haga al menos
// n * n / 4 comparaciones. make bench-sorts la mide.
inline std::vector<int> slow_input(std::size_t n) {
    (void)n;
    not_implemented("slow_input");
}

#endif