Efficient Algorithms for Sorting on GPUs

Sorting is an important problem in computing that has a rich history of investigation by various researchers. In this thesis we focus on this vital problem. In particular, we develop a novel algorithm for sorting on Graphics Processing Units (GPUs). GPUs are multicore architectures that offer the potential of affordable parallelism. We present an efficient sorting algorithm called Fine Sample Sort (FSS). Our FSS algorithm extends and outperforms sample sort algorithm presented by Leischner[2], which is currently the fastest known comparison based algorithm on GPUs. The performance gain of FSS is mainly achieved due to the quality of the samples selected. By quantitative and empirical approach, we found out the best way to select the samples, which resulted in an efficient sorting algorithm. We carried out the experiment for different input distributions, and found out that FSS outperforms sample sort by at least 26% and on an average by 37% for data sizes ranging from 40 million and above across various input distributions