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.
Funding Information
  • National Science Foundation (CCF-2103483,CCF-2238358,CCF-2339310,CNS-2317194,IIS-2227669)
  • UCR Regents Faculty Development Award
  • Google Research Scholar Program