What question did this study set out to answer?

The aim is to enhance the H-P sort algorithm using GPU technology for efficient integer sorting.

February 28, 2026

Efficient GPU-Implementation of a Sorting Algorithm Based on Histogram Computation and Prefix-Sums

Key Points

The aim is to enhance the H-P sort algorithm using GPU technology for efficient integer sorting.
Implemented a naive GPU version of the H-P sort algorithm.
Compared performance against CUB sort library for small input data ranges.
Optimized histogram and prefix-sum algorithms to improve speed.
Naive GPU implementation outperformed CUB sort for small input ranges.
Optimized version surpassed both naive H-P sort and CUB sort in key performance metrics.

Abstract

The H-P sort is a known algorithm for integer sorting using histogram computation and prefix sum calculation. In this paper, first, by implementing a naive GPU version of H-P sort, we demonstrate that it outperforms the fastest standard library (CUB sort) when the input data range is small compared to the input size. Next, by improving the histogram and prefix-sum algorithms, the optimized algorithm becomes faster than the naive version and, in some aspects where the H-P sort had previously been inferior to the CUB sort, it now outperforms.

Bookmark

Cite This Study

TAKASE et al. (Thu,) studied this question.

synapsesocial.com/papers/69a288060a974eb0d3c03ff3 https://doi.org/https://doi.org/10.1142/s0129626426500052

Bookmark