The C++ algorithm inplace_merge function is employed to merge two sorted ranges [first, last) and [middle, last) consecutively into a single sorted range [first, last).
Elements are compared using the < operator in the initial version or by utilizing the provided binary evaluation function comp in the subsequent version.
Syntax
default (1) template <class BidirectionalIterator>
void inplace_merge (BidirectionalIterator first, BidirectionalIterator middle,
BidirectionalIterator last);
custom (2) template <class BidirectionalIterator, class Compare>
void inplace_merge (BidirectionalIterator first, BidirectionalIterator middle,
BidirectionalIterator last, Compare comp);
Parameter
A bidirectional iterator that points to the initial element in the first of two adjacent sorted ranges that will be merged and sorted into a unified range.
last : A bidirectional iterator that points to the element just before the last element in the second of two adjacent sorted ranges that will be merged and sorted into a single range.
A bidirectional iterator positioned at the start of the second sorted range to merge and sort with the first range to create a unified sorted range.
The comp parameter is a custom binary predicate function that evaluates two arguments and outputs true if they are in the correct order, otherwise false. This function adheres to the principles of strict weak ordering to arrange the elements.
Return value
Complexity
If there is adequate additional memory accessible, the time complexity becomes linear in the gap between the initial and final positions: it executes N-1 comparisons and potentially double the number of element movements.
Otherwise, the complexity is linearithmic, carrying out a maximum of N*log(N) element comparisons, where N represents the difference between last and first, and also involving a maximum of that number of element swaps.
Data races
The elements within the range [first, last) are altered.
Exceptions
This function will raise an exception if any errors occur during element comparison, element swaps, or iterator operations.
Note: The invalid parameters cause an undefined behavior.
Example 1
Let's explore a straightforward example to illustrate the functionality of inplace_merge:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void printVector(vector<int>& v)
{
for (vector<int>::iterator it = v.begin(); it != v.end(); ++it)
cout << ' ' << *it;
cout << '\n';
}
int main () {
vector<int> v1 = {5,10,15,20,25}, v2 = {50,40,30,20,10}, v3(10);
vector<int>::iterator it;
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
it = copy(v1.begin(), v1.end(), v3.begin());
copy(v2.begin(), v2.end(), it);
inplace_merge(v3.begin(), it, v3.end());
cout << "Vector v1 : ";
printVector(v1);
cout << "Vector v2 : ";
printVector(v2);
cout << "Vector v3 : ";
printVector(v3);
}
Output:
Vector v1 : 5 10 15 20 25
Vector v2 : 10 20 30 40 50
Vector v3 : 5 10 10 15 20 20 25 30 40 50
Example 2
Let's see another simple example:
#include <iostream> // std::cout
#include <algorithm> // std::inplace_merge, std::sort, std::copy
#include <vector> // std::vector
using namespace std;
int main () {
int first[] = {5,10,15,20,25};
int second[] = {50,40,30,20,10};
vector<int> v(10);
vector<int>::iterator it;
sort (first,first+5);
sort (second,second+5);
it=copy (first, first+5, v.begin());
copy (second,second+5,it);
inplace_merge (v.begin(),v.begin()+5,v.end());
cout << "The resulting vector contains:";
for (it=v.begin(); it!=v.end(); ++it)
cout << ' ' << *it;
cout << '\n';
return 0;
}
Output:
The resulting vector contains: 5 10 10 15 20 20 25 30 40 50
Example 3
Let's explore another basic example showcasing the utilization of inplace_merge with the operator< function:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void) {
vector<int> v = {1, 3, 2, 4, 5};
inplace_merge(v.begin(), v.begin() + 2, v.end());
for (auto it = v.begin(); it != v.end(); ++it)
cout << *it << endl;
return 0;
}
Output:
1
2
3
4
5
Example 4
Let's explore a basic illustration to showcase the application of inplace_merge with a custom comparator function:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool descending_sort(int a, int b) {
return (a > b);
}
int main(void) {
vector<int> v = {3, 1, 5, 4, 2};
inplace_merge(v.begin(), v.begin() + 2, v.end(), descending_sort);
for (auto it = v.begin(); it != v.end(); ++it)
cout << *it << endl;
return 0;
}
Output:
5
4
3
2
1
Example 5
Let's see another simple example:
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
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);
inplace_merge(first, middle, last);
}
}
int main()
{
vector<int> v{10, 2, -9, 0, 9, 7, 1, 3, 4};
merge_sort(v.begin(), v.end());
for(auto n : v) {
cout << n << ' ';
}
cout << '\n';
return 0;
}
Output:
-9 0 1 2 3 4 7 9 10
