2010/02/24 by Frank Dehne, Dehne, Frank, Hamidreza Zaboli +1
Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Machine Learning and Data Classification #Parallel #Parallel Computing and Optimization Techniques #Stochastic Gradient Optimization Techniques #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1002.4464
openalex publication_date 2010/02/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present and evaluate GPU Bucket Sort, a parallel deterministic sample sort algorithm for many-core GPUs. Our method is considerably faster than Thrust Merge (Satish et.al., Proc. IPDPS 2009), the best comparison-based sorting algorithm for GPUs, and it is as fast as the new randomized sample sort for GPUs by Leischner et.al. (to appear in Proc. IPDPS 2010). Our deterministic sample sort has the advantage that bucket sizes are guaranteed and therefore its running time does not have the input data dependent fluctuations that can occur for randomized sample sort.