inplace_merge

| Home | Libraries | People | FAQ | More

##### 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:

- `BidirectionalRange` is a model of the Bidirectional Range Concept.
- `BidirectionalRange` is mutable.
- `range_value<BidirectionalRange>::type` is a model of `LessThanComparableConcept`
- The ordering on objects of `range_type<BidirectionalRange>::type` is a strict weak ordering, as defined in the `LessThanComparableConcept` requirements.

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:

- `middle` is in the range `rng`.
- `[begin(rng), middle)` is in ascending order. That is for each pair of adjacent elements `[x,y]`, `y < x` is `false`.
- `[middle, end(rng))` is in ascending order. That is for each pair of adjacent elements `[x,y]`, `y < x` is `false`.

###### For the predicate version:

- `middle` is in the range `rng`.
- `[begin(rng), middle)` is in ascending order. That is for each pair of adjacent elements `[x,y]`, `pred(y,x) == false`.
- `[middle, end(rng))` is in ascending order. That is for each pair of adjacent elements `[x,y]`, `pred(y,x) == false`.

###### Complexity

Worst case: `O(N log(N))`