A Customizable Interface for Samplesort and Radix Sort

Abstract

Sorting is one of the most widely studied problems in computer science. Many parallel algorithms exist for both comparison and integer sort. In our project we focus on Samplesort, a variation of Quicksort using multiple pivots selected from a sample of the input sequence. We are interested in improving its performance on shared-memory architecture. Samplesort can be deconstructed into primitives — pivot selection, partitioning into buckets, base case sort, and recursion. Different implementations of these primitives have been developed in the literature for specific purposes, such as reducing auxiliary space usage and taking advantage of vectorization. However, these specialized primitives may not perform well outside of their niche. Our work focuses on creating a general-purpose Samplesort which will conveniently deliver the best combination of these primitives for each user’s needs, which we achieve by designing a customizable interface in which different versions of the primitives can be inserted. We will implement and benchmark different combinations of leading variants, as well as our own variants, of each of the primitives on a variety of data types and input distributions, then analyze the results to determine which combinations function the best in different situations. By design, future researchers will be able to add and benchmark their own primitives using our interface. Our research will offer greater understanding of Samplesort, and will make high-performance parallel comparison sort more convenient to benchmark for future researchers, as well as more accessible to users.