preprint · arXiv (Cornell University) · 2024

Parallel Integer Sort: Theory and Practice

Xiaojun Dong, Laxman Dhulipala, Yan Gu, Yihan Sun

Cited by 0Open access

Abstract

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.

Cite this paper

APA 7

Dong, X., Dhulipala, L., Gu, Y., & Sun, Y. (2024). Parallel Integer Sort: Theory and Practice. arXiv (Cornell University). https://doi.org/10.48550/arxiv.2401.00710

MLA 9

Dong, Xiaojun, et al. “Parallel Integer Sort: Theory and Practice.” arXiv (Cornell University), 2024, https://doi.org/10.48550/arxiv.2401.00710.

Chicago

Dong, Xiaojun, Laxman Dhulipala, Yan Gu, and Yihan Sun. 2024. “Parallel Integer Sort: Theory and Practice.” arXiv (Cornell University). https://doi.org/10.48550/arxiv.2401.00710.

Harvard

Dong, X. et al. (2024) ‘Parallel Integer Sort: Theory and Practice’, arXiv (Cornell University). Available at: https://doi.org/10.48550/arxiv.2401.00710.

BibTeX

@misc{dong2024parallel,
  title = {{Parallel Integer Sort: Theory and Practice}},
  author = {Dong, Xiaojun and Dhulipala, Laxman and Gu, Yan and Sun, Yihan},
  journal = {arXiv (Cornell University)},
  year = {2024},
  doi = {10.48550/arxiv.2401.00710}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.