[FEA]: Extend cub::DeviceSegmentedSort to support custom comparators
- Dominant language
- C++
- Stars
- 2.5k
- Forks
- 486
- Avg merge
- 2d 6h
- Merged PRs (30d)
- 295
Description
### Is this a duplicate?
- [X] I confirmed there appear to be no [duplicate issues](https://github.com/NVIDIA/cccl/issues) for this request and that I agree to the [Code of Conduct](CODE_OF_CONDUCT.md)
### Area
CUB
### Is your feature request related to a problem? Please describe.
I would like to be able to use `cub::DeviceSegmentedSort` with a custom comparison operator.
As @gevtushenko explained here https://github.com/NVIDIA/cccl/discussions/1061 this isn't possible today because the underlying implementation uses a radix-based sort.
### Describe the solution you'd like
We should add an overload of `DeviceSegmentedSort` that takes a custom comparator and dispatches to a non-radix-based implementation.
### Dependencies
- [ ] Extend `cub::BlockMergeSort` to support dynamically sized inputs (iterator-based API)
### Describe alternatives you've considered
The primary alternatives are:
- Materialize the concrete data compatible with radix-based sorting in memory
- Use `DeviceMergeSort` and embed the segment ids as part of the keys
### Additional context
The non-radix-based implementation of `DeviceSegmentedSort` would ideally use the existing Merge Sort functionality.
This means `DeviceSegmentedSort` with a custom comparator indirectly depends on extending `BlockMergeSort` to accept dynamically sized inputs (i.e., `[begin,end)` iterator-based API). This is because we need a variant of `BlockMergeSort` that can operate on segments larger than a single tile.
Contributor guide
Assessment
This issue has not been assessed yet.