Parallel Integer Sort: Theory and Practice

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, $\mathsf{\text{DovetailSort}}$, that is theoretically-efficient and has good practical performance. In particular, $\mathsf{\text{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 $\mathsf{\text{DovetailSort}}$ is to combine algorithmic ideas from both integer- and comparison-sorting algorithms. In our experiments, $\mathsf{\text{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.