Difference between revisions of "cpp/algorithm/inplace merge"

Revision as of 11:13, 15 December 2019

Merges two consecutive sorted ranges [first, middle) and [middle, last) into one non-decreasing range [first, last).

In C++17, a sequence [first, last) is said to be in non-decreasing order with respect to a comparator comp if for any iterator it in [first, last) other than first, the condition comp(*it, *(it - 1)) (i.e. *it < *(it - 1)) evaluates to false.

A sequence is said to be sorted with respect to a comparator comp if for any iterator it pointing to the sequence and any non-negative integer n such that it + n is a valid iterator pointing to an element of the sequence, comp(*(it + n), *it) evaluates to false.

This merge is stable, which means that for equivalent elements in the original two ranges, the elements from the first range (preserving their original order) precede the elements from the second range (preserving their original order).

Parameters

Return value

(none)

Complexity

Given N = std::distance(first, last)},

Exceptions

The overloads with a template parameter named ExecutionPolicy report errors as follows:

• If execution of a function invoked as part of the algorithm throws an exception and ExecutionPolicy is one of the standard policies, std::terminate is called. For any other ExecutionPolicy, the behavior is implementation-defined.
• If the algorithm fails to allocate memory, std::bad_alloc is thrown.

Notes

This function attempts to allocate a temporary buffer. If the allocation fails, the less efficient algorithm is chosen.

Possible implementation

See also the implementations in libstdc++ and libc++.

Example

#include <vector>
#include <iostream>
#include <algorithm>
 
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(auto n : v) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
}

-2 0 1 2 3 7 8 11 11

See also