TNL::Algorithms::Sorting::CUBMergeSort Struct Reference

CUDA merge sort using CUB's DeviceMergeSort. More...

#include <TNL/Algorithms/Sorting/CUBMergeSort.h>

Static Public Member Functions
template<typename Array>
static void	sort (Array &array)
	Sort array in ascending order.
template<typename Array, typename Compare>
static void	sort (Array &array, const Compare &compare)
	Sort array using custom comparison function.

Detailed Description

CUDA merge sort using CUB's DeviceMergeSort.

This class provides a wrapper for merge sort implementation from NVIDIA's CUB library. It uses the cub::DeviceMergeSort::SortKeys algorithm which performs a merge sort on device-resident data.

Merge sort differs from radix sort in several key aspects:

• Can handle arbitrary types (as long as they are LessThan Comparable) and custom comparison functors
• Is not guaranteed to be stable
• Typically slower than DeviceRadixSort for arithmetic types

Example

#include <iostream>
#include <TNL/Algorithms/Sorting/CUBMergeSort.h>
#include <TNL/Algorithms/fillRandom.h>
#include <TNL/Containers/Array.h>
#include <TNL/Devices/Cuda.h>
 
int
main( int argc, char* argv[] )
{
   const int size = 20;
 
   TNL::Containers::Array< int, TNL::Devices::Cuda > arr( size );
 
   /***
    * Fill the array with random integers.
    */
   TNL::Algorithms::fillRandom< TNL::Devices::Cuda >( arr.getData(), size, 0, 2 * size );
 
   std::cout << "Random array: " << arr << "\n";
 
   /***
    * Sort in ascending order.
    */
   TNL::Algorithms::Sorting::CUBMergeSort::sort( arr );
 
   std::cout << "Array sorted in ascending order: " << arr << "\n";
 
   return EXIT_SUCCESS;
}

Output

Random array: [ 13, 19, 7, 2, 5, 30, 15, 0, 16, 39, 16, 35, 33, 20, 24, 19, 19, 30, 12, 18 ]
Array sorted in ascending order: [ 0, 2, 5, 7, 12, 13, 15, 16, 16, 18, 19, 19, 19, 20, 24, 30, 30, 33, 35, 39 ]

See also

CUBRadixSort for a faster radix sort alternative (for arithmetic types)

https://nvidia.github.io/cccl/unstable/cub/api/structcub_1_1DeviceMergeSort.html

Member Function Documentation

sort() [1/2]

template<typename Array>

void TNL::Algorithms::Sorting::CUBMergeSort::sort ( Array & array )

inlinestatic

Sort array in ascending order.

Template Parameters

Array

is a type of container to be sorted. It must be TNL::Containers::Array or TNL::Containers::ArrayView with TNL::Devices::Cuda device type.

Parameters

array

The array to sort (will be modified in-place).

sort() [2/2]

template<typename Array, typename Compare>

void TNL::Algorithms::Sorting::CUBMergeSort::sort ( Array & array, const Compare & compare )

inlinestatic

Sort array using custom comparison function.

Parameters

array	The array to sort (will be modified in-place).
compare	Comparison function object that returns true if the first argument should be ordered before the second.

---

The documentation for this struct was generated from the following file:

• src/TNL/Algorithms/Sorting/CUBMergeSort.h