Parallel Integer Sort: Theory and Practice
For practitioners needing fast parallel sorting, this work offers both theoretical justification for existing methods and a new algorithm with practical performance gains.
This paper provides tighter theoretical bounds for existing parallel integer sort algorithms and introduces DovetailSort, a new algorithm that efficiently handles duplicate keys by combining integer- and comparison-sorting ideas. DovetailSort achieves competitive or better performance than state-of-the-art parallel sorting algorithms on various datasets.
Integer sorting is a fundamental problem in computer science. This paper studies parallel integer sort both in theory and in practice. In theory, we show tighter bounds for a class of existing practical integer sort algorithms, which provides a solid theoretical foundation for their widespread usage in practice and strong performance. In practice, we design a new integer sorting algorithm, \textsf{DovetailSort}, that is theoretically-efficient and has good practical performance. In particular, \textsf{DovetailSort} overcomes a common challenge in existing parallel integer sorting algorithms, which is the difficulty of detecting and taking advantage of duplicate keys. The key insight in \textsf{DovetailSort} is to combine algorithmic ideas from both integer- and comparison-sorting algorithms. In our experiments, \textsf{DovetailSort} achieves competitive or better performance than existing state-of-the-art parallel integer and comparison sorting algorithms on various synthetic and real-world datasets.