I have forgotten
my Password

Or login with:

  • Facebookhttp://facebook.com/
  • Googlehttps://www.google.com/accounts/o8/id
  • Yahoohttps://me.yahoo.com
ComputingStlAlgorithmsSet

inplace_merge

Merges two consecutive sorted ranges
+ View version details

Key Facts

Gyroscopic Couple: The rate of change of angular momentum (\inline \tau) = \inline I\omega\Omega (In the limit).
  • \inline I = Moment of Inertia.
  • \inline \omega = Angular velocity
  • \inline \Omega = Angular velocity of precession.


Blaise Pascal (1623-1662) was a French mathematician, physicist, inventor, writer and Catholic philosopher.

Leonhard Euler (1707-1783) was a pioneering Swiss mathematician and physicist.

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.

Return Value

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.
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