Library: Algorithms
Function
Algorithm that merges two sorted consecutive sequences into a single sorted sequence
#include <algorithm>
namespace std {
template <class BidirectionalIterator>
void inplace_merge(BidirectionalIterator start,
BidirectionalIterator mid,
BidirectionalIterator finish);
template <class BidirectionalIterator, class Compare>
void inplace_merge(BidirectionalIterator start,
BidirectionalIterator mid,
BidirectionalIterator finish,
Compare comp);
}
The inplace_merge() algorithm merges two sorted consecutive ranges [start, mid) and [mid, finish), and puts the result of the merge into the range [start, finish). The merge is stable, which means that if the two ranges contain equivalent elements, the elements from the first range always precede the elements from the second.
There are two versions of the inplace_merge() algorithm. The first version uses operator<() as the default for comparison, and the second version accepts a third argument that specifies a binary predicate function object.
When enough additional memory is available, inplace_merge() does at most (finish - start) - 1 comparisons. If no additional memory is available, an algorithm with O(N * log(N)) complexity may be used, where N is equal to finish - start.
//
// merge.cpp
//
#include <algorithm> // advance, copy, inplace_merge, merge
#include <functional> // less
#include <iostream> // cout
#include <iterator> // back_inserter, ostream_iterator
#include <vector> // vector
int main ()
{
typedef std::vector<int, std::allocator<int> > Vector;
const Vector::value_type d1[] = { 1, 2, 3, 4};
const Vector::value_type d2[] = { 11, 13, 15, 17,
12, 14, 16, 18};
// Set up two vectors.
Vector v1 (d1 + 0, d1 + sizeof d1 / sizeof *d1);
Vector v2 (d1 + 0, d1 + sizeof d1 / sizeof *d1);
// Set up four destination vectors.
Vector v3 (d2 + 0, d2 + sizeof d2 / sizeof *d2);
Vector v4 (v3);
Vector v5 (v3);
Vector v6 (v3);
// Set up one empty vector.
Vector v7;
// Merge v1 with v2.
std::merge (v1.begin (), v1.end (),
v2.begin (), v2.end (), v3.begin ());
// Now use comparator.
std::merge (v1.begin (), v1.end (),
v2.begin (), v2.end (), v4.begin (),
std::less<int>());
// In place merge v5.
Vector::iterator mid = v5.begin ();
std::advance (mid, 4); // equivalent to mid += 4
// but more generic
std::inplace_merge (v5.begin (), mid, v5.end ());
// Now use a comparator on v6.
mid = v6.begin ();
std::advance (mid, 4); // equivalent to mid += 4
// but more generic
std::inplace_merge (v6.begin (), mid, v6.end (),
std::less<int>());
// Merge v1 and v2 to empty vector using insert iterator.
std::merge (v1.begin (), v1.end (),
v2.begin (), v2.end (),
std::back_inserter (v7));
// Copy all to cout.
std::ostream_iterator<int, char, std::char_traits<char> >
out (std::cout," ");
std::copy (v1.begin (), v1.end (), out);
std::cout << std::endl;
std::copy (v2.begin(), v2.end (), out);
std::cout << std::endl;
std::copy (v3.begin (), v3.end (), out);
std::cout << std::endl;
std::copy (v4.begin (), v4.end (), out);
std::cout << std::endl;
std::copy (v5.begin (), v5.end (), out);
std::cout << std::endl;
std::copy (v6.begin (),v6.end (), out);
std::cout << std::endl;
std::copy (v7.begin (), v7.end (), out);
std::cout << std::endl;
// Merge v1 and v2 to cout.
std::merge (v1.begin (), v1.end (),
v2.begin (), v2.end (), out);
return 0;
}
Program Output:
1 2 3 4 1 2 3 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 11 12 13 14 15 16 17 18 11 12 13 14 15 16 17 18 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4
ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 25.3.4