Related work

K-ary sorting algorithms can dramatically reduce movements compared to binary algorithms. Radix sorting algorithms go further and also reduce comparison cost, but are only available for certain data types and collation orders. Axtmann et al. (2017) have developed the k-ary In-place Parallel Super Scalar Samplesort (IPS4o) with the motivation to provide a more efficient alternative to quicksort variants in standard libraries. Their recent study improved and compared it to other algorithms including radix sorts and shows that IPS4o outperforms binary and other k-ary algorithms for sufficiently large data sets (Axtmann et al. 2022). Also their radix algorithms outperformed the quit generic library of Skarupke (2016). This C++ library of the KIT is highly recommended. Some limitations of IPS4o are its code complexity, that it is not stable and its limited adaptivity to presorted data.