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.

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.

References

Example 1

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

http://www.smu.ca/academic/science/compsci/

Example 2

Problem

This program illustrates the use of the STL inplace_merge() algorithm (extended version) to merge two ordered ranges of integer values in the same vector into a single ordered range of values within that same vector. The order of values is determined by one value preceding another if and only if the first has a smaller digit sum than the second.

Workings

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/* Tests if one integer has a smaller digit sum than another.
   i1 and i2 have been initialized and i1, i2 are both > 0.
   Returns true if sum of the digits in i1 is < sum of digits in i2, and otherwise returns false. */

bool hasSmallerDigitSum (int i1, int i2)
{
  int digitSum1 = 0;
  while (i1 != 0)
  {
    digitSum1 += i1 % 10;
    i1 /= 10;
  }

  int digitSum2 = 0;
  while (i2 != 0)
  {
    digitSum2 += i2 % 10;
    i2 /= 10;
  }
  return digitSum1 < digitSum2;
}

int main()
{
  int a[] = {11, 41 , 36, 59, 98, 21, 13, 6, 52, 44, 28, 69};
  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)<<" ";
  cout <<"\nNote that the first five values form the first range, "
         "\nand the rest of the values form the second range.";

  inplace_merge(v.begin(), v.begin()+5, v.end(), hasSmallerDigitSum);
  
  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:
11 41 36 59 98 21 13 6 52 44 28 69
Note that the first five values form the first range,
and the rest of the values form the second range.

Now we perform the "in place merge".
Here are the revised contents of v:
11 21 13 41 6 52 44 36 28 59 69 98

References

http://www.smu.ca/academic/science/compsci/

Definition

Interface

Description

Return Value

Complexity

References

Example 1

Example 2

See Also