text: //===----------------------------------------------------------------------===//
  //
  //                     The LLVM Compiler Infrastructure
  //
  // This file is dual licensed under the MIT and the University of Illinois Open
  // Source Licenses. See LICENSE.TXT for details.
  //
  //===----------------------------------------------------------------------===//
  
  // <algorithm>
  
  // template<InputIterator InIter1, InputIterator InIter2, typename OutIter>
  //   requires OutputIterator<OutIter, InIter1::reference>
  //         && OutputIterator<OutIter, InIter2::reference>
  //         && HasLess<InIter2::value_type, InIter1::value_type>
  //   OutIter
  //   merge(InIter1 first1, InIter1 last1, InIter2 first2, InIter2 last2, OutIter result);
  
  #include <algorithm>
  #include <cassert>
  
  #include "test_iterators.h"
  
  template <class InIter1, class InIter2, class OutIter>
  void
  test()
  {
      {
      unsigned N = 100000;
      int* ia = new int[N];
      int* ib = new int[N];
      int* ic = new int[2*N];
      for (unsigned i = 0; i < N; ++i)
          ia[i] = 2*i;
      for (unsigned i = 0; i < N; ++i)
          ib[i] = 2*i+1;
      OutIter r = std::merge(InIter1(ia), InIter1(ia+N),
                             InIter2(ib), InIter2(ib+N), OutIter(ic));
      assert(base(r) == ic+2*N);
      assert(ic[0] == 0);
      assert(ic[2*N-1] == 2*N-1);
      assert(std::is_sorted(ic, ic+2*N));
      delete [] ic;
      delete [] ib;
      delete [] ia;
      }
      {
      unsigned N = 100;
      int* ia = new int[N];
      int* ib = new int[N];
      int* ic = new int[2*N];
      for (unsigned i = 0; i < 2*N; ++i)
          ic[i] = i;
      std::random_shuffle(ic, ic+2*N);
      std::copy(ic, ic+N, ia);
      std::copy(ic+N, ic+2*N, ib);
      std::sort(ia, ia+N);
      std::sort(ib, ib+N);
      OutIter r = std::merge(InIter1(ia), InIter1(ia+N),
                             InIter2(ib), InIter2(ib+N), OutIter(ic));
      assert(base(r) == ic+2*N);
      assert(ic[0] == 0);
      assert(ic[2*N-1] == 2*N-1);
      assert(std::is_sorted(ic, ic+2*N));
      delete [] ic;
      delete [] ib;
      delete [] ia;
      }
  }
  
  int main()
  {
      test<input_iterator<const int*>, input_iterator<const int*>, output_iterator<int*> >();
      test<input_iterator<const int*>, input_iterator<const int*>, forward_iterator<int*> >();
      test<input_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >();
      test<input_iterator<const int*>, input_iterator<const int*>, random_access_iterator<int*> >();
      test<input_iterator<const int*>, input_iterator<const int*>, int*>();
  
      test<input_iterator<const int*>, forward_iterator<const int*>, output_iterator<int*> >();
      test<input_iterator<const int*>, forward_iterator<const int*>, forward_iterator<int*> >();
      test<input_iterator<const int*>, forward_iterator<const int*>, bidirectional_iterator<int*> >();
      test<input_iterator<const int*>, forward_iterator<const int*>, random_access_iterator<int*> >();
      test<input_iterator<const int*>, forward_iterator<const int*>, int*>();
  
      test<input_iterator<const int*>, bidirectional_iterator<const int*>, output_iterator<int*> >();
      test<input_iterator<const int*>, bidirectional_iterator<const int*>, forward_iterator<int*> >();
      test<input_iterator<const int*>, bidirectional_iterator<const int*>, bidirectional_iterator<int*> >();
      test<input_iterator<const int*>, bidirectional_iterator<const int*>, random_access_iterator<int*> >();
      test<input_iterator<const int*>, bidirectional_iterator<const int*>, int*>();
  
      test<input_iterator<const int*>, random_access_iterator<const int*>, output_iterator<int*> >();
      test<input_iterator<const int*>, random_access_iterator<const int*>, forward_iterator<int*> >();
      test<input_iterator<const int*>, random_access_iterator<const int*>, bidirectional_iterator<int*> >();
      test<input_iterator<const int*>, random_access_iterator<const int*>, random_access_iterator<int*> >();
      test<input_iterator<const int*>, random_access_iterator<const int*>, int*>();
  
      test<input_iterator<const int*>, const int*, output_iterator<int*> >();
      test<input_iterator<const int*>, const int*, forward_iterator<int*> >();
      test<input_iterator<const int*>, const int*, bidirectional_iterator<int*> >();
      test<input_iterator<const int*>, const int*, random_access_iterator<int*> >();
      test<input_iterator<const int*>, const int*, int*>();
  
      test<forward_iterator<const int*>, input_iterator<const int*>, output_iterator<int*> >();
      test<forward_iterator<const int*>, input_iterator<const int*>, forward_iterator<int*> >();
      test<forward_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >();
      test<forward_iterator<const int*>, input_iterator<const int*>, random_access_iterator<int*> >();
      test<forward_iterator<const int*>, input_iterator<const int*>, int*>();
  
      test<forward_iterator<const int*>, forward_iterator<const int*>, output_iterator<int*> >();
      test<forward_iterator<const int*>, forward_iterator<const int*>, forward_iterator<int*> >();
      test<forward_iterator<const int*>, forward_iterator<const int*>, bidirectional_iterator<int*> >();
      test<forward_iterator<const int*>, forward_iterator<const int*>, random_access_iterator<int*> >();
      test<forward_iterator<const int*>, forward_iterator<const int*>, int*>();
  
      test<forward_iterator<const int*>, bidirectional_iterator<const int*>, output_iterator<int*> >();
      test<forward_iterator<const int*>, bidirectional_iterator<const int*>, forward_iterator<int*> >();
      test<forward_iterator<const int*>, bidirectional_iterator<const int*>, bidirectional_iterator<int*> >();
      test<forward_iterator<const int*>, bidirectional_iterator<const int*>, random_access_iterator<int*> >();
      test<forward_iterator<const int*>, bidirectional_iterator<const int*>, int*>();
  
      test<forward_iterator<const int*>, random_access_iterator<const int*>, output_iterator<int*> >();
      test<forward_iterator<const int*>, random_access_iterator<const int*>, forward_iterator<int*> >();
      test<forward_iterator<const int*>, random_access_iterator<const int*>, bidirectional_iterator<int*> >();
      test<forward_iterator<const int*>, random_access_iterator<const int*>, random_access_iterator<int*> >();
      test<forward_iterator<const int*>, random_access_iterator<const int*>, int*>();
  
      test<forward_iterator<const int*>, const int*, output_iterator<int*> >();
      test<forward_iterator<const int*>, const int*, forward_iterator<int*> >();
      test<forward_iterator<const int*>, const int*, bidirectional_iterator<int*> >();
      test<forward_iterator<const int*>, const int*, random_access_iterator<int*> >();
      test<forward_iterator<const int*>, const int*, int*>();
  
      test<bidirectional_iterator<const int*>, input_iterator<const int*>, output_iterator<int*> >();
      test<bidirectional_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >();
      test<bidirectional_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >();
      test<bidirectional_iterator<const int*>, input_iterator<const int*>, random_access_iterator<int*> >();
      test<bidirectional_iterator<const int*>, input_iterator<const int*>, int*>();
  
      test<bidirectional_iterator<const int*>, forward_iterator<const int*>, output_iterator<int*> >();
      test<bidirectional_iterator<const int*>, forward_iterator<const int*>, forward_iterator<int*> >();
      test<bidirectional_iterator<const int*>, forward_iterator<const int*>, bidirectional_iterator<int*> >();
      test<bidirectional_iterator<const int*>, forward_iterator<const int*>, random_access_iterator<int*> >();
      test<bidirectional_iterator<const int*>, forward_iterator<const int*>, int*>();
  
      test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*>, output_iterator<int*> >();
      test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*>, forward_iterator<int*> >();
      test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*>, bidirectional_iterator<int*> >();
      test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*>, random_access_iterator<int*> >();
      test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*>, int*>();
  
      test<bidirectional_iterator<const int*>, random_access_iterator<const int*>, output_iterator<int*> >();
      test<bidirectional_iterator<const int*>, random_access_iterator<const int*>, forward_iterator<int*> >();
      test<bidirectional_iterator<const int*>, random_access_iterator<const int*>, bidirectional_iterator<int*> >();
      test<bidirectional_iterator<const int*>, random_access_iterator<const int*>, random_access_iterator<int*> >();
      test<bidirectional_iterator<const int*>, random_access_iterator<const int*>, int*>();
  
      test<bidirectional_iterator<const int*>, const int*, output_iterator<int*> >();
      test<bidirectional_iterator<const int*>, const int*, forward_iterator<int*> >();
      test<bidirectional_iterator<const int*>, const int*, bidirectional_iterator<int*> >();
      test<bidirectional_iterator<const int*>, const int*, random_access_iterator<int*> >();
      test<bidirectional_iterator<const int*>, const int*, int*>();
  
      test<random_access_iterator<const int*>, input_iterator<const int*>, output_iterator<int*> >();
      test<random_access_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >();
      test<random_access_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >();
      test<random_access_iterator<const int*>, input_iterator<const int*>, random_access_iterator<int*> >();
      test<random_access_iterator<const int*>, input_iterator<const int*>, int*>();
  
      test<random_access_iterator<const int*>, forward_iterator<const int*>, output_iterator<int*> >();
      test<random_access_iterator<const int*>, forward_iterator<const int*>, forward_iterator<int*> >();
      test<random_access_iterator<const int*>, forward_iterator<const int*>, bidirectional_iterator<int*> >();
      test<random_access_iterator<const int*>, forward_iterator<const int*>, random_access_iterator<int*> >();
      test<random_access_iterator<const int*>, forward_iterator<const int*>, int*>();
  
      test<random_access_iterator<const int*>, bidirectional_iterator<const int*>, output_iterator<int*> >();
      test<random_access_iterator<const int*>, bidirectional_iterator<const int*>, forward_iterator<int*> >();
      test<random_access_iterator<const int*>, bidirectional_iterator<const int*>, bidirectional_iterator<int*> >();
      test<random_access_iterator<const int*>, bidirectional_iterator<const int*>, random_access_iterator<int*> >();
      test<random_access_iterator<const int*>, bidirectional_iterator<const int*>, int*>();
  
      test<random_access_iterator<const int*>, random_access_iterator<const int*>, output_iterator<int*> >();
      test<random_access_iterator<const int*>, random_access_iterator<const int*>, forward_iterator<int*> >();
      test<random_access_iterator<const int*>, random_access_iterator<const int*>, bidirectional_iterator<int*> >();
      test<random_access_iterator<const int*>, random_access_iterator<const int*>, random_access_iterator<int*> >();
      test<random_access_iterator<const int*>, random_access_iterator<const int*>, int*>();
  
      test<random_access_iterator<const int*>, const int*, output_iterator<int*> >();
      test<random_access_iterator<const int*>, const int*, forward_iterator<int*> >();
      test<random_access_iterator<const int*>, const int*, bidirectional_iterator<int*> >();
      test<random_access_iterator<const int*>, const int*, random_access_iterator<int*> >();
      test<random_access_iterator<const int*>, const int*, int*>();
  
      test<const int*, input_iterator<const int*>, output_iterator<int*> >();
      test<const int*, input_iterator<const int*>, bidirectional_iterator<int*> >();
      test<const int*, input_iterator<const int*>, bidirectional_iterator<int*> >();
      test<const int*, input_iterator<const int*>, random_access_iterator<int*> >();
      test<const int*, input_iterator<const int*>, int*>();
  
      test<const int*, forward_iterator<const int*>, output_iterator<int*> >();
      test<const int*, forward_iterator<const int*>, forward_iterator<int*> >();
      test<const int*, forward_iterator<const int*>, bidirectional_iterator<int*> >();
      test<const int*, forward_iterator<const int*>, random_access_iterator<int*> >();
      test<const int*, forward_iterator<const int*>, int*>();
  
      test<const int*, bidirectional_iterator<const int*>, output_iterator<int*> >();
      test<const int*, bidirectional_iterator<const int*>, forward_iterator<int*> >();
      test<const int*, bidirectional_iterator<const int*>, bidirectional_iterator<int*> >();
      test<const int*, bidirectional_iterator<const int*>, random_access_iterator<int*> >();
      test<const int*, bidirectional_iterator<const int*>, int*>();
  
      test<const int*, random_access_iterator<const int*>, output_iterator<int*> >();
      test<const int*, random_access_iterator<const int*>, forward_iterator<int*> >();
      test<const int*, random_access_iterator<const int*>, bidirectional_iterator<int*> >();
      test<const int*, random_access_iterator<const int*>, random_access_iterator<int*> >();
      test<const int*, random_access_iterator<const int*>, int*>();
  
      test<const int*, const int*, output_iterator<int*> >();
      test<const int*, const int*, forward_iterator<int*> >();
      test<const int*, const int*, bidirectional_iterator<int*> >();
      test<const int*, const int*, random_access_iterator<int*> >();
      test<const int*, const int*, int*>();
  }
  