Parallel Integer Sort: Theory and Practice

• DOI: 10.48550/arxiv.2401.00710
• Publication Date: 2024-01-01
• Authors: Xiaojun Dong; Laxman Dhulipala; Yan Gu; Yihan Sun

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