Node:Merge, Next:, Previous:Binary search, Up:Sorting and related operations


Merge

OutputIterator merge (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result) Function
OutputIterator merge (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp) Function 

template 
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
                     InputIterator2 first2, InputIterator2 last2,
                     OutputIterator result);

template 
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
                     InputIterator2 first2, InputIterator2 last2,
                     OutputIterator result, Compare comp);

merge merges two sorted ranges [first1, last1) and [first2, last2) into the range [result, result + (last1 - first1) + (last2 - first2)). The merge is stable, that is, for equal elements in the two ranges, the elements from the first range always precede the elements from the second. merge returns result + (last1 - first1) + (last2 - first2). At most (last1 - first1) + (last2 - first2) - 1 comparisons are performed. The result of merge is undefined if the resulting range overlaps with either of the original ranges.

inplace_merge (BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last); Function
inplace_merge (BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp); Function 

template 
void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle,
                   BidirectionalIterator last);

template 
void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle,
                   BidirectionalIterator last, Compare comp);

inplace_merge merges two sorted consecutive ranges [first, middle) and [middle, last) putting the result of the merge into the range [first, last). The merge is stable, that is, for equal elements in the two ranges, the elements from the first range always precede the elements from the second. When enough additional memory is available, at most (last - first) - 1 comparisons are performed. If no additional memory is available, an algorithm with O(N \log N) complexity may be used.