Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext
inplace_merge
Prototype

template<class BidirectionalRange>
BidirectionalRange&
inplace_merge( BidirectionalRange& rng,
               typename range_iterator<BidirectionalRange>::type middle );

template<class BidirectionalRange>
const BidirectionalRange&
inplace_merge( const BidirectionalRange& rng,
               typename range_iterator<const BidirectionalRange>::type middle );

template<class BidirectionalRange, class BinaryPredicate>
BidirectionalRange&
inplace_merge( BidirectionalRange& rng,
               typename range_iterator<BidirectionalRange>::type middle,
               BinaryPredicate pred );

template<class BidirectionalRange, class BinaryPredicate>
const BidirectionalRange&
inplace_merge( const BidirectionalRange& rng,
               typename range_iterator<const BidirectionalRange>::type middle,
               BinaryPredicate pred );

Description

inplace_merge combines two consecutive sorted ranges [begin(rng), middle) and [middle, end(rng)) into a single sorted range [begin(rng), end(rng)). That is, it starts with a range [begin(rng), end(rng)) that consists of two pieces each of which is in ascending order, and rearranges it so that the entire range is in ascending order. inplace_merge is stable, meaning both that the relative order of elements within each input range is preserved.

Definition

Defined in the header file boost/range/algorithm/inplace_merge.hpp

Requirements

For the non-predicate version:

For the predicate version: * BidirectionalRange is a model of the Bidirectional Range Concept. * BidirectionalRange is mutable. * BinaryPredicate is a model of the StrictWeakOrderingConcept. * BidirectionalRange's value type is convertible to both BinaryPredicate's argument types.

Precondition:
For the non-predicate version:
For the predicate version:
Complexity

Worst case: O(N log(N))


PrevUpHomeNext