Efficient GPU-Implementation of a Sorting Algorithm Based on Histogram Computation and Prefix-Sums
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.
Fields of Study & Subjects
Parallel Computing and Optimization Techniques
Computer Graphics and Visualization Techniques
Algorithms and Data Compression
Publication details
- Journal / source
- Parallel Processing Letters
- Volume
- 36
- Issue
- 01n02
- Publication date
- 26 February 2026
- Language
- EN