template <class BidirectionalIterator>
inline void inplace_merge(BidirectionalIterator first,
                          BidirectionalIterator middle,
                          BidirectionalIterator last);
 
template <class BidirectionalIterator, class StrictWeakOrdering>
inline void inplace_merge(BidirectionalIterator first,
                          BidirectionalIterator middle,
                          BidirectionalIterator last, StrictWeakOrdering comp);

Algorytm zawarty w Standard Template Library. Funkcja inplace_merge() łączy dwa uporządkowane rosnąco zakresy [first, middle) oraz [middle, last) w jeden zakres [first, last) uporządkowany rosnąco. Algorytm jest stabilny. W pierwszej wersji funkcji do porównywania elementów używany jest operator< . W drugiej wersji możliwe jest dostarczenie własnego funktora testującego poprzedzanie elementów. Funkcja testująca pobiera 2 argumenty i zwraca wartość logiczną TRUE w przypadku, gdy pierwszy argument poprzedza drugi; jeśli zamienimy argumenty miejscami otrzymamy FALSE.

Złożoność pesymistyczna algorytmu to O(N log(N)).

#include <algorithm>

• first - iterator wskazujący początek pierwszego zakresu
• middle - iterator wskazujący koniec pierwszego zakresu i jednocześnie początek drugiego zakresu
• last - iterator wskazujący koniec drugiego zakresu
• comp - argument opcjonalny, wskaźnik na funkcję testującą poprzedzanie drugiego obiektu przez pierwszy

• Inicjalizacja struktur danych

    std::list<int> container, containerDesc, containerDivis;
    std::list<int>::iterator it;
 
    container.push_back(13);        containerDesc.push_back(13);        containerDivis.push_back(2);        
    container.push_back(15);        containerDesc.push_back(11);        containerDivis.push_back(8);
    container.push_back(17);        containerDesc.push_back(9);         containerDivis.push_back(32);
    container.push_back(19);        containerDesc.push_back(7);         containerDivis.push_back(128);
 
    container.push_back(8);         containerDesc.push_back(20);        containerDivis.push_back(1);
    container.push_back(10);        containerDesc.push_back(12);        containerDivis.push_back(4);
    container.push_back(14);        containerDesc.push_back(8);         containerDivis.push_back(16);
    container.push_back(18);        containerDesc.push_back(5);         containerDivis.push_back(64);
    container.push_back(28);        containerDesc.push_back(0);         containerDivis.push_back(1024);

• Próba użycia algorytmu przy niespełnionym warunku uporządkowania jednego z zakresów

zakres pierwszy: 13, 15, 17
zakres drugi: 19, 8, 10, 14, 18, 28
Na wyjściu otrzymamy niepożądaną kolejność elementów (w tym przypadku niezmienioną)

    std::inplace_merge(container.begin(), ++(++(++container.begin())), container.end());
 
    std::cout << "wynik dzialania funkcji przy braku uporzadkowania rosnacego:" << std::endl;
    for(it = container.begin(); it != container.end(); ++it)
             std::cout << *it << " ";
    std::cout << std::endl <<std::endl;

• Najprostsze użycie algorytmu inplace_merge tworzące jeden rosnąco posortowany zakres z dwóch oddzielnie uporządkowanych

zakres pierwszy: 13, 15, 17, 19
zakres drugi: 8, 10, 14, 18, 28

    std::inplace_merge(container.begin(), ++(++(++(++container.begin()))), container.end());
 
    std::cout << "zawartosc container'a po wykonaniu inplace_merge to:" << std::endl;
    for(it = container.begin(); it != container.end(); ++it)
             std::cout << *it << " ";
    std::cout << std::endl <<std::endl;

• Wykorzystanie opcjonalnego argumentu funkcji inplace_merge()

Załóżmy że chcemy uzyskać uporządkowanie malejące z dwóch malejących zakresów.
Do tego celu posłużę się funktorem greater<T> (nagłówek: #include <functional>).
zakres pierwszy: 13, 11, 9, 7
zakres drugi: 20, 12, 8, 5, 0

    std::inplace_merge(containerDesc.begin(), ++(++(++(++containerDesc.begin()))), containerDesc.end(), std::greater<int>());
 
    std::cout << "zawartosc containerDesc'a po wykonaniu inplace_merge z odwroconym uporzadkowaniem to:" << std::endl;
    for(it = containerDesc.begin(); it != containerDesc.end(); ++it)
             std::cout << *it << " ";
    std::cout << std::endl <<std::endl;

• Wykorzystanie opcjonalnego argumentu funkcji inplace_merge()

Tym razem utworzyłem funkcję bool divisible(int, int), która zwraca TRUE w przypadku gdy drugi argument jest podzielny przez pierwszy, w przeciwnym wypadku FALSE
funkcja zostanie wykorzystana przez inplace_merge

/**
 * Funkcja testująca podzielność drugiego argumentu przez pierwszy
 * Zwraca TRUE w przypadku gdy drugi argument jest podzielny przez pierwszy, w przeciwnym wypadku FALSE
 */
const bool divisible(const int &arg1, const int &arg2)
{
    return !(arg2 % arg1);
}

zakres pierwszy: 2, 8, 32, 128
zakres drugi: 1, 4, 16, 64, 1024

    std::inplace_merge(containerDivis.begin(), ++(++(++(++containerDivis.begin()))), containerDivis.end(), divisible);
 
    std::cout << "zawartosc containerDivis'a po wykonaniu inplace_merge z dostarczona funkcja divisible:" << std::endl;
    for(it = containerDivis.begin(); it != containerDivis.end(); ++it)
             std::cout << *it << " ";
    std::cout << std::endl <<std::endl;

inplace_merge_algorithm.cpp