I have forgotten

• https://me.yahoo.com

# inplace_merge

Merges two consecutive sorted ranges

## Definition

The inplace_merge() algorithm is defined in the standard header <algorithm> and in the nonstandard backward-compatibility header <algo.h>.

## Interface

```#include <algorithm>
template < class BidirectionalIterator >
void inplace_merge(
BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last
);
template < class BidirectionalIterator, class Predicate >
void inplace_merge(
BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last,
Predicate comp
);```

Parameters:
Parameter Description
first A bidirectional iterator addressing the position of the first element in the first of two consecutive sorted ranges to be combined and sorted into a single range
middle A bidirectional iterator addressing the position of the first element in the second of two consecutive sorted ranges to be combined and sorted into a single range
last A bidirectional iterator addressing the position one past the last element in the second of two consecutive sorted ranges to be combined and sorted into a single range
comp User-defined predicate function object that defines the sense in which one element is greater than another. The binary predicate takes two arguments and should return `true` when the first element is less than the second element and `false` otherwise

## Description

Inplace_merge function merges two consecutive sorted ranges `[first, middle)` and `[middle, last)` into one sorted range `[first, last)`. The order of equal elements is guaranteed to be preserved.

The first version compares objects using `operator<`, and the second compares objects using a function object `comp`.

None.

## Complexity

The complexity is linear; performs `(last - first) - 1` if enough additional memory is available.
Otherwise, is N log(N), where `N = last - first`.

### References

Example:

##### Example - inplace_merge function
Problem
This program illustrates the use of the STL inplace_merge() algorithm (default version) to merge two sorted ranges of integer values in the same vector into a single sorted range of values within that same vector.
Workings
```#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
int a[] = {1, 3 , 5, 7, 9, 11, 13, 2, 4, 6, 8, 10};
vector<int> v(a, a+12);

cout <<"\nHere are the contents of v:\n";
for (vector<int>::size_type i=0; i<v.size(); i++)
cout <<v.at(i)<<" ";

inplace_merge(v.begin(), v.begin()+7, v.end());

cout <<"\nNow we perform the "in place merge".";
cout <<"\nHere are the revised contents of v:\n";
for (vector<int>::size_type i=0; i<v.size(); i++)
cout <<v.at(i)<<" ";

return 0;
}```
Solution
Output:

Here are the contents of v:
1 3 5 7 9 11 13 2 4 6 8 10

Now we perform the "in place merge".
Here are the revised contents of v:
1 2 3 4 5 6 7 8 9 10 11 13
References