Merges two consecutivesorted ranges[first, middle) and[middle, last) into onesorted range[first, last).

A sequence is said to besorted with respect to the comparatorcomp and projectionproj if for any iteratorit pointing to the sequence and any non-negative integern such thatit + n is a valid iterator pointing to an element of the sequence,std::invoke(comp,std::invoke(proj,*(it+ n)),std::invoke(proj,*it))) evaluates tofalse.

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

The function-like entities described on this page arealgorithm function objects (informally known asniebloids), that is:

• Explicit template argument lists cannot be specified when calling any of them.
• None of them are visible toargument-dependent lookup.
• When any of them are found bynormal unqualified lookup as the name to the left of the function-call operator,argument-dependent lookup is inhibited.

[edit]Parameters

[edit]Return value

An iterator equal tolast.

[edit]Complexity

ExactlyN −1 comparisons, if additional memory buffer is available, whereN=ranges::distance(first, last). Otherwise,\(\scriptsize \mathcal{O}(N\cdot\log{(N)})\)𝓞(N•log(N)) comparisons. Additionally, twice as many projections as comparisons in both cases.

[edit]Notes

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

[edit]Possible implementation

This implementation only shows the slower algorithm used when no additional memory is available. See also the implementation inMSVC STL andlibstdc++.

struct inplace_merge_fn{template<std::bidirectional_iterator I,std::sentinel_for<I> S,class Comp=ranges::less,class Proj=std::identity>    requiresstd::sortable<I, Comp, Proj>constexpr I operator()(I first, I middle, S last, Comp comp={}, Proj proj={})const{        I last_it=ranges::next(middle, last);        inplace_merge_slow(first, middle, last_it,ranges::distance(first, middle),ranges::distance(middle, last_it),std::ref(comp),std::ref(proj));return last_it;} template<ranges::bidirectional_range R,class Comp=ranges::less,class Proj=std::identity>    requiresstd::sortable<ranges::iterator_t<R>, Comp, Proj>constexprranges::borrowed_iterator_t<R>        operator()(R&& r,ranges::iterator_t<R> middle,                   Comp comp={}, Proj proj={})const{return(*this)(ranges::begin(r), std::move(middle),ranges::end(r),                       std::move(comp), std::move(proj));} private:template<class I,class Comp,class Proj>staticconstexprvoid inplace_merge_slow(I first, I middle, I last,std::iter_difference_t<I> n1,std::iter_difference_t<I> n2,                                             Comp comp, Proj proj){if(n1==0|| n2==0)return;if(n1+ n2==2&& comp(proj(*middle), proj(*first))){ranges::iter_swap(first, middle);return;}         I cut1= first, cut2= middle;std::iter_difference_t<I> d1{}, d2{}; if(n1> n2){            d1= n1/2;ranges::advance(cut1, d1);            cut2=ranges::lower_bound(middle, last,*cut1,std::ref(comp),std::ref(proj));            d2=ranges::distance(middle, cut2);}else{            d2= n2/2;ranges::advance(cut2, d2);            cut1=ranges::upper_bound(first, middle,*cut2,std::ref(comp),std::ref(proj));            d1=ranges::distance(first, cut1);}         I new_middle=ranges::rotate(cut1, middle, cut2);        inplace_merge_slow(first, cut1, new_middle, d1, d2,std::ref(comp),std::ref(proj));        inplace_merge_slow(new_middle, cut2, last, n1- d1, n2- d2,std::ref(comp),std::ref(proj));}}; inlineconstexpr inplace_merge_fn inplace_merge{};

[edit]Example

#include <algorithm>#include <complex>#include <functional>#include <iostream>#include <iterator>#include <vector> void print(autoconst& v,autoconst& rem,int middle=-1){for(int i{};auto n: v)std::cout<<(i++== middle?"│ ":"")<< n<<' ';std::cout<< rem<<'\n';} template<std::random_access_iterator I,std::sentinel_for<I> S>requiresstd::sortable<I>void merge_sort(I first, S last){if(last- first>1){        I middle{first+(last- first)/2};        merge_sort(first, middle);        merge_sort(middle, last);        std::ranges::inplace_merge(first, middle, last);}} int main(){// custom merge-sort demostd::vector v{8,2,0,4,9,8,1,7,3};    print(v,": before sort");    merge_sort(v.begin(), v.end());    print(v,": after sort\n"); // merging with comparison function object and projectionusing CI=std::complex<int>;std::vector<CI> r{{0,1},{0,2},{0,3},{1,1},{1,2}};constauto middle{std::ranges::next(r.begin(),3)};auto comp{std::ranges::less{}};auto proj{[](CI z){return z.imag();}};     print(r,": before merge", middle- r.begin());    std::ranges::inplace_merge(r, middle, comp, proj);    print(r,": after merge");}

8 2 0 4 9 8 1 7 3 : before sort0 1 2 3 4 7 8 8 9 : after sort (0,1) (0,2) (0,3) │ (1,1) (1,2) : before merge(0,1) (1,1) (0,2) (1,2) (0,3) : after merge

[edit]See also

• In other languages

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