Normal Merge algorithm is basically merging to sorted sequences but it has a time and space complexity of O(m+n) where m and n are the sizes of the corresponding sequences.

But std::inplace_merge is different, it does merging within the same container between two ranges [first,middle) and [middle,last) where the ranges must be sorted beforehand.

Since it is inplace that means no additional space is required.

SYNTAX:-

version 1

template <class IteratorLoc>
  void inplace_merge (IteratorLoc first, IteratorLoc middle, IteratorLoc last);

version 2

template <class IteratorLoc, class Compare_function>
  void inplace_merge (IteratorLoc first, IteratorLoc middle, IteratorLoc last, Compare_function function_name);



PARAMETERS-

first - iterator to the first position of the first range.
middle - iterator of the intial position of the second sorted sequence of the container.
last - iterator of the last position of the second sorted sequence of the container.
function_name - is the function pointer of the bool fucntion which returns true or false after comparision.


COMPLEXTY-

If enough extra memory is available, linear in the distance between first and last: Performs N-1 comparisons and up to twice that many element moves.
Otherwise, up to linearithmic: Performs up to N*log(N) element comparisons (where N is the distance above), and up to that many element swaps.

IN THIS ARTICLE WE ARE SEEING HOW TO USE THIS ALGORITH HEADER FUCNTION ON vector  CONTAINER.

code example :-

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// inplace_merge example
#include <iostream>     
#include <algorithm>    // std::inplace_merge, std::sort, std::copy
#include <vector>       // std::vector


//including this to able to use all the required things from standard namespace
using namespace std;

//bool function for comparison
bool myfunction (int i,int j) { return (i<j); }

int main () {
	
  int first_half[] = {50,1,5,3,15};
  int second_half[] = {0,-20,9,20,777};
  vector<int> v1;
  vector<int> v2;
  
  sort (first_half,first_half+5);
  sort (second_half,second_half+5);
  
  //pushing values in the vector container v1
  for (int i = 0; i <sizeof(first_half)/sizeof(int); i++) 
    {
		v1.push_back(first_half[i]); 
	}
  for (int i = 0; i <sizeof(second_half)/sizeof(int); i++) 
    {
    	v1.push_back(second_half[i]); 
    }   


  //using version 1	
  inplace_merge (v1.begin(),v1.begin()+5,v1.end());
  cout << "The resulting vector contains: using version 1";
  for (int i=0;i<10;i++)
  {
	cout << ' ' << v1[i];
  }
  
  
  //pushing values in the vector container v2
  for (int i = 0; i <sizeof(first_half)/sizeof(int); i++) 
    {
		v2.push_back(first_half[i]); 
	}
  for (int i = 0; i <sizeof(second_half)/sizeof(int); i++) 
    {
    	v2.push_back(second_half[i]); 
    } 

  
  //using version 2
  inplace_merge (v2.begin(),v2.begin()+5,v2.end(),myfunction);
  cout << "\nThe resulting vector contains: using version 2";
  for (int i=0;i<10;i++)
  {
	cout << ' ' << v2[i];
  }	
  
  return 0;
}







NOTE :- cant be done with other container as there is no implementation of operator +.