2026-07-23T20:03:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13775 2024-03-06T10:52:55Z ddc:004 open_access

Fast and Robust Vectorized In-Place Sorting of Primitive Types Blacher, Mark Giesen, Joachim Kühne, Lars Quicksort Sorting Networks Vectorization SIMD AVX2 Modern CPUs provide single instruction-multiple data (SIMD) instructions. SIMD instructions process several elements of a primitive data type simultaneously in fixed-size vectors. Classical sorting algorithms are not directly expressible in SIMD instructions. Accelerating sorting algorithms with SIMD instruction is therefore a creative endeavor. A promising approach for sorting with SIMD instructions is to use sorting networks for small arrays and Quicksort for large arrays. In this paper we improve vectorization techniques for sorting networks and Quicksort. In particular, we show how to use the full capacity of vector registers in sorting networks and how to make vectorized Quicksort robust with respect to different key distributions. To demonstrate the performance of our techniques we implement an in-place hybrid sorting algorithm for the data type int with AVX2 intrinsics. Our implementation is at least 30% faster than state-of-the-art high-performance sorting alternatives. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mark Blacher and Joachim Giesen and Lars Kühne 2021 Is Part Of LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2021.3 urn:nbn:de:0030-drops-137758 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.3 eng https://creativecommons.org/licenses/by/4.0/legalcode