Accelerate Implementation of Timsort Algorithm Using CUDA
Dilara Yasmin Disha, Md. Nazrul Islam Mondal · 2023
Sorting algorithms are fundamental in various computing applications.In this paper, we introduce a CUDA-based acceleration of the Timsort algorithm, leveraging the parallel processing of GPUs. Our implementation strategically decomposes the sorting process into parallel tasks, effectively surmounting inherent challenges related to synchronization and load balancing. Our experimental findings reveal a substantial speedup compared to CPU-based Timsort implementations. This acceleration renders our approach highly promising for real-world applications. Notably, our results demonstrate that the Timsort algorithm achieves a remarkable speed enhancement ranging from 22x to 48x when employing CUDA, relative to CPU-based executions, across diverse dataset sizes. These findings underscore the efficacy and applicability of our CUDA-accelerated Timsort in addressing the growing demand for faster sorting algorithms in contemporary computing scenarios.