thrust::merge

Overloads

merge(exec, first1, last1, first2, last2, result)

template<typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator>
OutputIterator thrust::merge(

const thrust::detail::execution_policy_base<DerivedPolicy> &exec,

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<.

The algorithm’s execution is parallelized as determined by exec.

The following code snippet demonstrates how to use merge to compute the merger of two sorted sets of integers using the thrust::host execution policy for parallelization:

#include <thrust/merge.h>
#include <thrust/execution_policy.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(thrust::host,
                A1, A1 + 6,
                A2, A2 + 7,
                result);
// result = {1, 1, 1, 2, 3, 3, 5, 5, 7, 8, 9, 11, 13}

See also

https://en.cppreference.com/w/cpp/algorithm/merge

See also

set_union

See also

sort

See also

is_sorted

Parameters:

• exec – The execution policy to use for parallelization.

• 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.

Template Parameters:

• DerivedPolicy – The name of the derived execution policy.

• 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 convertible 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 convertible to a type in OutputIterator's set of value_types.

• OutputIterator – is a model of Output Iterator.

Returns:

The end of the output range.

Pre:

The ranges [first1, last1) and [first2, last2) shall be sorted with respect to operator<.

Pre:

The resulting range shall not overlap with either input range.

merge(first1, last1, first2, last2, result)

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<.

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

https://en.cppreference.com/w/cpp/algorithm/merge

See also

set_union

See also

sort

See also

is_sorted

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.

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 convertible 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 convertible to a type in OutputIterator's set of value_types.

• OutputIterator – is a model of Output Iterator.

Returns:

The end of the output range.

Pre:

The ranges [first1, last1) and [first2, last2) shall be sorted with respect to operator<.

Pre:

The resulting range shall not overlap with either input range.

merge(exec, first1, last1, first2, last2, result, comp)

template<typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator, typename StrictWeakCompare>
OutputIterator thrust::merge(

const thrust::detail::execution_policy_base<DerivedPolicy> &exec,

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.

The algorithm’s execution is parallelized as determined by exec.

The following code snippet demonstrates how to use merge to compute the merger of two sets of integers sorted in descending order using the thrust::host execution policy for parallelization:

#include <thrust/merge.h>
#include <thrust/functional.h>
#include <thrust/execution_policy.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(thrust::host,
                                A1, A1 + 6,
                                A2, A2 + 7,
                                result,
                                ::cuda::std::greater<int>());
// result = {13, 11, 9, 8, 7, 5, 5, 3, 3, 2, 1, 1, 1}

See also

https://en.cppreference.com/w/cpp/algorithm/merge

See also

sort

See also

is_sorted

Parameters:

• exec – The execution policy to use for parallelization.

• 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.

Template Parameters:

• DerivedPolicy – The name of the derived execution policy.

• InputIterator1 – is a model of Input Iterator, InputIterator1's value_type is convertible to StrictWeakCompare's first argument type. and InputIterator1's value_type is convertible to a type in OutputIterator's set of value_types.

• InputIterator2 – is a model of Input Iterator, InputIterator2's value_type is convertible to StrictWeakCompare's second argument type. and InputIterator2's value_type is convertible 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.

Returns:

The end of the output range.

Pre:

The ranges [first1, last1) and [first2, last2) shall be sorted with respect to comp.

Pre:

The resulting range shall not overlap with either input range.

merge(first1, last1, first2, last2, result, comp)

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.

The following code snippet demonstrates how to use merge to compute the merger of two sets of integers sorted in descending 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, ::cuda::std::greater<int>());
// result = {13, 11, 9, 8, 7, 5, 5, 3, 3, 2, 1, 1, 1}

See also

https://en.cppreference.com/w/cpp/algorithm/merge

See also

sort

See also

is_sorted

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.

Template Parameters:

• InputIterator1 – is a model of Input Iterator, InputIterator1's value_type is convertible to StrictWeakCompare's first argument type. and InputIterator1's value_type is convertible to a type in OutputIterator's set of value_types.

• InputIterator2 – is a model of Input Iterator, InputIterator2's value_type is convertible to StrictWeakCompare's second argument type. and InputIterator2's value_type is convertible 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.

Returns:

The end of the output range.

Pre:

The ranges [first1, last1) and [first2, last2) shall be sorted with respect to comp.

Pre:

The resulting range shall not overlap with either input range.