Merging

Functions
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator >
OutputIterator	thrust::merge (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename StrictWeakCompare >
OutputIterator	thrust::merge (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakCompare comp)

---

Function Documentation

template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator >

OutputIterator thrust::merge	(	InputIterator1	first1,
		InputIterator1	last1,
		InputIterator2	first2,
		InputIterator2	last2,
		OutputIterator	result
	)

merge combines two sorted ranges [first1, last1) and [first2, last2) into a single sorted range. That is, it copies from [first1, last1) and [first2, last2) into [result, result + (last1 - first1) + (last2 - first2)) such that the resulting range is in ascending order. merge is stable, meaning both that the relative order of elements within each input range is preserved, and that for equivalent elements in both input ranges the element from the first range precedes the element from the second. The return value is result + (last1 - first1) + (last2 - first2).

This version of merge compares elements using operator<.

Parameters:

first1	The beginning of the first input range.
last1	The end of the first input range.
first2	The beginning of the second input range.
last2	The end of the second input range.
result	The beginning of the merged output.

Returns:

The end of the output range.

Template Parameters:

InputIterator1	is a model of Input Iterator, InputIterator1 and InputIterator2 have the same value_type, InputIterator1's value_type is a model of LessThan Comparable, the ordering on InputIterator1's value_type is a strict weak ordering, as defined in the LessThan Comparable requirements, and InputIterator1's value_type is convertable to a type in OutputIterator's set of value_types.
InputIterator2	is a model of Input Iterator, InputIterator2 and InputIterator1 have the same value_type, InputIterator2's value_type is a model of LessThan Comparable, the ordering on InputIterator2's value_type is a strict weak ordering, as defined in the LessThan Comparable requirements, and InputIterator2's value_type is convertable to a type in OutputIterator's set of value_types.
OutputIterator	is a model of Output Iterator.

The following code snippet demonstrates how to use merge to compute the merger of two sorted sets of integers.

  #include <thrust/merge.h>
  ...
  int A1[6] = {1, 3, 5, 7, 9, 11};
  int A2[7] = {1, 1, 2, 3, 5,  8, 13};

  int result[13];

  int *result_end = thrust::merge(A1, A1 + 6, A2, A2 + 7, result);
  // result = {1, 1, 1, 2, 3, 3, 5, 5, 7, 8, 9, 11, 13}

See also:

http://www.sgi.com/tech/stl/merge.html

set_union

sort

is_sorted

template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename StrictWeakCompare >

OutputIterator thrust::merge	(	InputIterator1	first1,
		InputIterator1	last1,
		InputIterator2	first2,
		InputIterator2	last2,
		OutputIterator	result,
		StrictWeakCompare	comp
	)

merge combines two sorted ranges [first1, last1) and [first2, last2) into a single sorted range. That is, it copies from [first1, last1) and [first2, last2) into [result, result + (last1 - first1) + (last2 - first2)) such that the resulting range is in ascending order. merge is stable, meaning both that the relative order of elements within each input range is preserved, and that for equivalent elements in both input ranges the element from the first range precedes the element from the second. The return value is result + (last1 - first1) + (last2 - first2).

This version of merge compares elements using a function object comp.

Parameters:

first1	The beginning of the first input range.
last1	The end of the first input range.
first2	The beginning of the second input range.
last2	The end of the second input range.
result	The beginning of the merged output.
comp	Comparison operator.

Returns:

The end of the output range.

Template Parameters:

InputIterator1	is a model of Input Iterator, InputIterator1's value_type is convertable to StrictWeakCompare's first_argument_type. and InputIterator1's value_type is convertable to a type in OutputIterator's set of value_types.
InputIterator2	is a model of Input Iterator, InputIterator2's value_type is convertable to StrictWeakCompare's second_argument_type. and InputIterator2's value_type is convertable to a type in OutputIterator's set of value_types.
OutputIterator	is a model of Output Iterator.
StrictWeakCompare	is a model of Strict Weak Ordering.

The following code snippet demonstrates how to use merge to compute the merger of two sets of integers sorted in ascending order.

  #include <thrust/merge.h>
  #include <thrust/functional.h>
  ...
  int A1[6] = {11, 9, 7, 5, 3, 1};
  int A2[7] = {13, 8, 5, 3, 2, 1, 1};

  int result[13];

  int *result_end = thrust::merge(A1, A1 + 6, A2, A2 + 7, result, thrust::greater<int>());
  // result = {13, 11, 9, 8, 7, 5, 5, 3, 3, 2, 1, 1, 1}

See also:

http://www.sgi.com/tech/stl/merge.html

sort

is_sorted