inplace_merge

inplace_merge

template<class BidIt>
    void inplace_merge(BidIt first, BidIt middle, BidIt last);
template<class BidIt, class Pred>
    void inplace_merge(BidIt first, BidIt middle, BidIt last, Pred pr);

The first template function reorders the sequences designated by iterators in the ranges [first, middle) and [middle, last), each ordered byoperator<, to form a merged sequence of length last - first beginning at first, also ordered by operator<. The merge occurs without altering the relative order of elements within either original sequence. Moreover, for any two elements from different original sequences that have equivalent ordering, the element from the ordered range [first, middle) precedes the other.

The function evaluates the ordering predicate X < Y at most ceil((last - first) * log(last - first)) times. (Given enough temporary storage, it can evaluate the predicate (last - first) - 1 times, at most.)

The second template function behaves the same, except that it replaces operator<(X, Y) with pr(X, Y).

Sample programs: inplace_merge and inplace_merge (predicate version).