Engineering In-place (Shared-memory) Sorting Algorithms
Open Access
- 31 January 2022
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Parallel Computing
- Vol. 9 (1) , 1-62
Abstract
We present new sequential and parallel sorting algorithms that now represent the fastest known techniques for a wide range of input sizes, input distributions, data types, and machines. Somewhat surprisingly, part of the speed advantage is due to the additional feature of the algorithms to work in-place, i.e., they do not need a significant amount of space beyond the input array. Previously, the in-place feature often implied performance penalties. Our main algorithmic contribution is a blockwise approach to in-place data distribution that is provably cache-efficient. We also parallelize this approach taking dynamic load balancing and memory locality into account. Our new comparison-based algorithm In-place Parallel Super Scalar Samplesort ( IPS 4 o ) , combines this technique with branchless decision trees. By taking cases with many equal elements into account and by adapting the distribution degree dynamically, we obtain a highly robust algorithm that outperforms the best previous in-place parallel comparison-based sorting algorithms by almost a factor of three. That algorithm also outperforms the best comparison-based competitors regardless of whether we consider in-place or not in-place, parallel or sequential settings. Another surprising result is that IPS 4 o even outperforms the best (in-place or not in-place) integer sorting algorithms in a wide range of situations. In many of the remaining cases (often involving near-uniform input distributions, small keys, or a sequential setting), our new In-place Parallel Super Scalar Radix Sort ( IPS 2 Ra ) turns out to be the best algorithm. Claims to have the – in some sense – “best” sorting algorithm can be found in many papers which cannot all be true. Therefore, we base our conclusions on an extensive experimental study involving a large part of the cross product of 21 state-of-the-art sorting codes, 6 data types, 10 input distributions, 4 machines, 4 memory allocation strategies, and input sizes varying over 7 orders of magnitude. This confirms the claims made about the robust performance of our algorithms while revealing major performance problems in many competitors outside the concrete set of measurements reported in the associated publications. This is particularly true for integer sorting algorithms giving one reason to prefer comparison-based algorithms for robust general-purpose sorting.Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- An in-place sorting with O ( n log n ) comparisons and O ( n ) movesJournal of the ACM, 2005
- Quicksort without a stack2005
- Benchmarking optimization software with performance profilesMathematical Programming, 2002
- A perspective on QuicksortComputing in Science & Engineering, 2000
- A survey of adaptive sorting algorithmsACM Computing Surveys, 1992
- Time-space optimal parallel merging and sortingIEEE Transactions on Computers, 1991
- Parallel Quicksort using fetch-and-addIEEE Transactions on Computers, 1990
- A one-way, stackless quicksort algorithmBIT Numerical Mathematics, 1986
- How not to lie with statistics: the correct way to summarize benchmark resultsCommunications of the ACM, 1986
- Sorting on Electronic Computer SystemsJournal of the ACM, 1956