A comparison-free sorting algorithm on CPUs and GPUs.

This paper presents a new sorting algorithm that sorts input data elements without any comparison operations between the data—comparison-free sorting. Our algorithm’s time complexity is on the order of O(N) for both single- and multi-threaded CPU and many-core GPU implementations. Our results show speedups on average of 4.6 × , 4 × , and 3.5 × for single-threaded CPU, 8-threaded CPU, and many-threaded GPU implementations, respectively, for input sizes ranging from 27 to 230 elements as compared to common sorting algorithms for a wide variation of element distributions, ranging from all unique elements to a single repeated element. In addition, our proposed algorithm more efficiently utilizes the GPU architecture as compared to a multi-core CPU architecture, showing a speedup of approximately 4 × for input sizes ranging from 27 to 230 elements. [ABSTRACT FROM AUTHOR]