Efficient GPU-Implementation for Integer Sorting Based on Histogram and Prefix-Sums

In this paper, we propose integer sorting algorithms based on histogram and prefix-sums and we show that their GPU-implementations are faster than the fastest sorting GPU-implementations in Thrust and/or CUB library for several input data. In particular, our algorithm is very useful in the cases that the maximum value of input data is smaller than the number of input data and/or the number of kinds of input data is smaller than the maximum value of input data.