Merge two sorted sequences

Source code

Declaration

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

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

template <class BidirectionalIterator>
inline void inplace_merge(BidirectionalIterator first,
                          BidirectionalIterator middle,
                          BidirectionalIterator last);

template <class BidirectionalIterator, class Compare>
inline void inplace_merge(BidirectionalIterator first,
                          BidirectionalIterator middle,
                          BidirectionalIterator last, Compare comp);

Description The merge functions merge the two sorted ranges [ first1, last1) and [ first2, last2) into the range of size n beginning at result , where n is the sum of the size of the ranges [ first1, last1) and [ first2, last2) , and returns the past-the-end iterator for the merged sequence. The merge of the two sorted sequences results in a sorted sequence. The merge is stable, meaning that for equal elements in the two ranges, the element from the range [ first1, last1) will always precede the element from the range [ first2, last2) . Element comparisons are performed using operator< for the first merge function, and are performed using the function object comp for the second merge function.

The inplace_merge functions merge the two sorted consecutive ranges [ first, middle) and [ middle, last) , placing the result in the range [ first, last) . The inplace merge of the two sorted sequences results in a sorted sequence. The inplace merge is stable, meaning that for equal elements in the two ranges, the element from the range [ first, middle) will always precede the element from the range [ first2, last2) . Element comparisons are performed using operator< for the first inplace_merge function, and are performed using the function object comp for the second inplace_merge function.

Type requirements

• InputIterator1 and InputIterator2 must be at least input iterators .
• OutputIterator must be at least an output iterator .
• BidirectionalIterator must be at least a regular bidirectional iterator .
• For the merge functions, Compare must be a function object type that provides int operator()(T1, T2), where T1 and T2 are the dereference types of \ InputIterator2 and InputIterator1, respectively. For the inplace_merge functions, Compare must be a function object type that provides int operator()(S, S), where S is the dereference type of \ BidirectionalIterator.

Group Sorting and related operations.

Time complexity Linear for the merge functions, and at most

for the inplace_merge functions, where n is the size of the range [ first, last) .

The merge functions perform n + m assignments and at most n + m - 1 comparisons, where n is the size of the range [ first1, last1) and m is the size of the range [ first2, last2) .

The inplace_merge functions require linear time and perform a linear number of assignments if enough buffer memory is available for the adaptive algorithm to place a sequence in the buffer, otherwise time is required and at most assignments are performed, where n is the size of the range [ first, last) . In either case, at most n comparisons are required, where n is the size of the range [ first, last) .

Space complexity Constant for the merge functions, and at most linear for the inplace_merge functions.

The inplace_merge functions require linear space for buffer if the adaptive algorithm is used and the buffer is large enough to have one of the sequences placed in it, otherwise logarithmic space is required for recursive function calls (linear space may also be used for some buffer size that is not large enough to contain either of the sequences).

Mutative? Yes.

Example Select here to view the source code for the example.

Implementation Select here to view source code (Copyright (C) 1994, Hewlett-Packard Company) for this algorithm.