Parallel Integer Sort: Theory and Practice
Preprint
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.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- On the Hardness and Approximation of Euclidean DBSCANACM Transactions on Database Systems, 2017
- GPU-Accelerated Large-Scale Distributed Sorting Coping with Device Memory CapacityIEEE Transactions on Big Data, 2016
- Ray Specialized Contraction on Bounding Volume HierarchiesComputer Graphics Forum, 2015
- In-place permuting and perfect shuffling using involutionsInformation Processing Letters, 2013
- Partitioned Parallel Radix SortJournal of Parallel and Distributed Computing, 2002
- Sorting in Linear Time?Journal of Computer and System Sciences, 1998
- Space-Efficient Scheduling of Multithreaded ComputationsSIAM Journal on Computing, 1998
- Improved Parallel Integer Sorting without Concurrent WritingInformation and Computation, 1997
- On parallel hashing and integer sortingJournal of Algorithms, 1991
- Optimal and Sublogarithmic Time Randomized Parallel Sorting AlgorithmsSIAM Journal on Computing, 1989