inplace_merge function template — Merges sorted, adjacent ranges in place
template<typename BidiIter> void inplace_merge(BidiIter first, BidiIter middle, BidiIter last); template<typename BidiIter, typename Compare> void inplace_merge(BidiIter first, BidiIter middle, BidiIter last, Compare comp);
The inplace_merge
function
template merges two sorted, consecutive ranges in place, creating a
single sorted range. The two ranges are [first
, middle
) and [middle
, last
). The resulting range is [first
, last
).
The merge is stable, so elements retain their respective orders, with equivalent elements in the first range coming before elements in the second.
Both sequences must be sorted. The first form uses the
<
operator to compare
elements. The second form calls comp(*iter1
, *iter2)
.
Figure 13-7 shows
how inplace_merge
operates.
Precondition: !(*(i
+ 1)
< *i
) for all i
in [first
, middle
- 1) and !(*(j
+ 1) < *j
) for all
j
in [middle
,
last
- 1).
Postcondition: !(*(i
+ 1)
< *i
) for all i
in [first
, last
- 1).
Complexity is usually linear with n
+ 1 comparisons, but if enough
temporary memory is not available, the complexity might be n
log n
, in which n
is last
- first
.