# In-place Parallel Super Scalar Samplesort (IPS4o)

arXiv: https://arxiv.org/abs/1705.02257 · HTML: https://mlsanity.com/paper/1705.02257/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 May 2017.

## Built on by (most cited first, 1 of 1)

- [tSPM+; a high-performance algorithm for mining transitive sequential patterns from clinical data](https://mlsanity.com/paper/2309.05671/) (2023)

## Abstract (arXiv)

We present a sorting algorithm that works in-place, executes in parallel, is cache-efficient, avoids branch-mispredictions, and performs work O(n log n) for arbitrary inputs with high probability. The main algorithmic contributions are new ways to make distribution-based algorithms in-place: On the practical side, by using coarse-grained block-based permutations, and on the theoretical side, we show how to eliminate the recursion stack. Extensive experiments show that our algorithm IPS4o scales well on a variety of multi-core machines. We outperform our closest in-place competitor by a factor of up to 3. Even as a sequential algorithm, we are up to 1.5 times faster than the closest sequential competitor, BlockQuicksort.