Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2017.9
URN: urn:nbn:de:0030-drops-78542
URL: https://drops.dagstuhl.de/opus/volltexte/2017/7854/
Axtmann, Michael ; Witt, Sascha ; Ferizovic, Daniel ; Sanders, Peter
In-Place Parallel Super Scalar Samplesort (IPSSSSo)
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{axtmann_et_al:LIPIcs:2017:7854,
author = {Michael Axtmann and Sascha Witt and Daniel Ferizovic and Peter Sanders},
title = {{In-Place Parallel Super Scalar Samplesort (IPSSSSo)}},
booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)},
pages = {9:1--9:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-049-1},
ISSN = {1868-8969},
year = {2017},
volume = {87},
editor = {Kirk Pruhs and Christian Sohler},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7854},
URN = {urn:nbn:de:0030-drops-78542},
doi = {10.4230/LIPIcs.ESA.2017.9},
annote = {Keywords: shared memory, parallel sorting, in-place algorithm, comparison-based sorting, branch prediction}
}
| Keywords: | shared memory, parallel sorting, in-place algorithm, comparison-based sorting, branch prediction | |
| Seminar: | 25th Annual European Symposium on Algorithms (ESA 2017) | |
| Issue date: | 2017 | |
| Date of publication: | 01.09.2017 |
