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 datacomparison-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.6x, 4x, and 3.5xfor single-threaded CPU, 8-threaded CPU, and many-threaded GPU implementations, respectively, for input sizes ranging from 2(7) to 2(30) 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 4x for input sizes ranging from 2(7) to 2(30) elements.