Parallel Integer Sort: Theory and Practice (Abstract) | Proceedings of the 2024 ACM Workshop on Highlights of Parallel Computing
Open Access
- 17 June 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 13-14
Abstract
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, DovetailSort, that is theoretically efficient and has good practical performance.Keywords
Funding Information
- National Science Foundation (CCF-2103483,CCF-2238358,CCF-2339310,CNS-2317194,IIS-2227669)
- UCR Regents Faculty Development Award
- Google Research Scholar Program
This publication has 6 references indexed in Scilit:
- Engineering In-place (Shared-memory) Sorting AlgorithmsACM Transactions on Parallel Computing, 2022
- ParlayLib - A Toolkit for Parallel Algorithms on Shared-Memory Multicore Machines2020
- Theoretically-Efficient and Practical Parallel In-Place Radix Sorting2019
- Even Faster Sorting of (Not Only) Integers2017
- Low depth cache-oblivious algorithms2010
- Improved Parallel Integer Sorting without Concurrent WritingInformation and Computation, 1997