C++ <algorithm> - merge() Function

The C++ algorithm::merge function is used to merge elements of sorted ranges [first1, last1) and [first2, last2) to the range starting at result. In default version elements are compared using operator< and in custom version elements are compared using comp.

Syntax

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

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

Parameters

`first1`	Specify initial position of the input iterator1. The range used is [first1,last1).
`last1`	Specify final position of the input iterator1. The range used is [first1,last1).
`first2`	Specify initial position of the input iterator2. The range used is [first2,last2).
`last2`	Specify final position of the input iterator2. The range used is [first2,last2).
`result`	Specify initial position of the output iterator where the result to be stored.
`comp`	Specify a binary function that accepts two elements pointed by the iterators, and returns a value convertible to bool. The returned value indicates which element will go first.

Return Value

Returns an iterator pointing to the past-the-end element of result sequence.

Time Complexity

Up to Linear i.e, Θ(n).

Example:

In the example below, the algorithm::merge function is used to merge two sorted arrays into a vector.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main (){
  int arr1[] = {10, 20, 30, 40, 50};
  int arr2[] = {10, 15, 20, 25, 30};
  vector<int> vec(10);
  vector<int>::iterator it;

  //merge arr1 and arr2 into vec
  merge(arr1, arr1+5, arr2, arr2+5, vec.begin());

  cout<<"vec contains:";
  for(it = vec.begin(); it != vec.end(); ++it)
    cout<<" "<<*it;

  return 0;
}

The output of the above code will be:

vec contains: 10 10 15 20 20 25 30 30 40 50

❮ C++ <algorithm> Library