2026-07-23T19:18:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7854 2024-03-06T10:41:16Z ddc:004 open_access

In-Place Parallel Super Scalar Samplesort (IPSSSSo) Axtmann, Michael Witt, Sascha Ferizovic, Daniel Sanders, Peter shared memory parallel sorting in-place algorithm comparison-based sorting branch prediction 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 shw that our algorithm IPSSSSo 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Axtmann and Sascha Witt and Daniel Ferizovic and Peter Sanders 2017 Is Part Of LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2017.9 urn:nbn:de:0030-drops-78542 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.9 eng https://creativecommons.org/licenses/by/3.0/legalcode