std:: inplace_merge

Combina dos rangos ordenados consecutivos [ first , middle ) y [ middle , last ) en un único rango ordenado [ first , last ) .

Esta función de fusión es estable, lo que significa que para elementos equivalentes en los dos rangos originales, los elementos del primer rango (preservando su orden original) preceden a los elementos del segundo rango (preservando su orden original).

Si se satisface cualquiera de las siguientes condiciones, el comportamiento es indefinido:

• [ first , middle ) o [ middle , last ) no es un rango válido .

Parámetros

Complejidad

Dado \(\scriptsize N\) N como std:: distance ( first, last ) :

Excepciones

Las sobrecargas con un parámetro de plantilla llamado ExecutionPolicy reportan errores de la siguiente manera:

• Si la ejecución de una función invocada como parte del algoritmo lanza una excepción y ExecutionPolicy es uno de los standard policies , std::terminate es llamado. Para cualquier otro ExecutionPolicy , el comportamiento está definido por la implementación.
• Si el algoritmo falla al asignar memoria, std::bad_alloc es lanzado.

Implementación posible

Vea las implementaciones en libstdc++ y libc++ .

Notas

Esta función intenta asignar un búfer temporal. Si la asignación falla, se elige el algoritmo menos eficiente.

Ejemplo

#include <algorithm>
#include <iostream>
#include <vector>
template<class Iter>
void merge_sort(Iter first, Iter last)
{
    if (last - first > 1)
    {
        Iter middle = first + (last - first) / 2;
        merge_sort(first, middle);
        merge_sort(middle, last);
        std::inplace_merge(first, middle, last);
    }
}
int main()
{
    std::vector<int> v{8, 2, -2, 0, 11, 11, 1, 7, 3};
    merge_sort(v.begin(), v.end());
    for (const auto& n : v)
        std::cout << n << ' ';
    std::cout << '\n';
}

-2 0 1 2 3 7 8 11 11

Véase también