1[/ 2 Copyright 2010 Neil Groves 3 Distributed under the Boost Software License, Version 1.0. 4 (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 5/] 6[section:inplace_merge inplace_merge] 7 8[heading Prototype] 9 10`` 11template<class BidirectionalRange> 12BidirectionalRange& 13inplace_merge( BidirectionalRange& rng, 14 typename range_iterator<BidirectionalRange>::type middle ); 15 16template<class BidirectionalRange> 17const BidirectionalRange& 18inplace_merge( const BidirectionalRange& rng, 19 typename range_iterator<const BidirectionalRange>::type middle ); 20 21template<class BidirectionalRange, class BinaryPredicate> 22BidirectionalRange& 23inplace_merge( BidirectionalRange& rng, 24 typename range_iterator<BidirectionalRange>::type middle, 25 BinaryPredicate pred ); 26 27template<class BidirectionalRange, class BinaryPredicate> 28const BidirectionalRange& 29inplace_merge( const BidirectionalRange& rng, 30 typename range_iterator<const BidirectionalRange>::type middle, 31 BinaryPredicate pred ); 32`` 33 34[heading Description] 35 36`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. 37 38[heading Definition] 39 40Defined in the header file `boost/range/algorithm/inplace_merge.hpp` 41 42[heading Requirements] 43 44[*For the non-predicate version:] 45 46* `BidirectionalRange` is a model of the __bidirectional_range__ Concept. 47* `BidirectionalRange` is mutable. 48* `range_value<BidirectionalRange>::type` is a model of `LessThanComparableConcept` 49* The ordering on objects of `range_type<BidirectionalRange>::type` is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements. 50 51[*For the predicate version:] 52* `BidirectionalRange` is a model of the __bidirectional_range__ Concept. 53* `BidirectionalRange` is mutable. 54* `BinaryPredicate` is a model of the `StrictWeakOrderingConcept`. 55* `BidirectionalRange`'s value type is convertible to both `BinaryPredicate`'s argument types. 56 57[heading Precondition:] 58 59[heading For the non-predicate version:] 60 61* `middle` is in the range `rng`. 62* `[begin(rng), middle)` is in ascending order. That is for each pair of adjacent elements `[x,y]`, `y < x` is `false`. 63* `[middle, end(rng))` is in ascending order. That is for each pair of adjacent elements `[x,y]`, `y < x` is `false`. 64 65[heading For the predicate version:] 66 67* `middle` is in the range `rng`. 68* `[begin(rng), middle)` is in ascending order. That is for each pair of adjacent elements `[x,y]`, `pred(y,x) == false`. 69* `[middle, end(rng))` is in ascending order. That is for each pair of adjacent elements `[x,y]`, `pred(y,x) == false`. 70 71[heading Complexity] 72 73Worst case: `O(N log(N))` 74 75[endsect] 76 77 78