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

This merge function 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).

If any of the following conditions is satisfied, the behavior is undefined:

• [first, middle) or[middle, last) is not avalid range.

[edit]Parameters

[edit]Complexity

Given\(\scriptsize N\)N asstd::distance(first, last):

[edit]Exceptions

The overloads with a template parameter namedExecutionPolicy report errors as follows:

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

[edit]Possible implementation

See the implementations inlibstdc++ andlibc++.

[edit]Notes

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

[edit]Example

#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(constauto& n: v)std::cout<< n<<' ';std::cout<<'\n';}

-2 0 1 2 3 7 8 11 11

[edit]See also

• In other languages

• Deutsch
• Español
• Français
• Italiano
• 日本語
• Português
• Русский
• 中文