Previous fileTop of DocumentContentsIndex pageNext file
Apache C++ Standard Library Reference Guide

inplace_merge()

Library:  Algorithms


Function

Local Index

No Entries

Summary

Algorithm that merges two sorted consecutive sequences into a single sorted sequence

Synopsis

#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);
}

Description

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.

Complexity

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.

Example

See Also

merge()

Standards Conformance

ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 25.3.4



Previous fileTop of DocumentContentsIndex pageNext file