2024/01/01 by Xiaojun Dong, Dong, Xiaojun, Laxman Dhulipala +5
Computer Science · #Algorithms and Data Compression #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2401.00710
openalex publication_date 2024/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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, \textsfDovetailSort, that is theoretically-efficient and has good practical performance. In particular, \textsfDovetailSort 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 \textsfDovetailSort is to combine algorithmic ideas from both integer- and comparison-sorting algorithms. In our experiments, \textsfDovetailSort achieves competitive or better performance than existing state-of-the-art parallel integer and comparison sorting algorithms on various synthetic and real-world datasets.