Fast Branchless Quicksort using Sorting-Networks with C and C++ Interface

Performance results naturally depend on the underlying hardware. The following benchmarks show the execution times for sorting 50 million doubles using different sorting implementations. The measurements were taken on an Apple M1 system using Clang and on an AMD Ryzen 3 Linux system using GCC , both compiled with the -O3 option.

Implementation Apple M1 AMD Ryzen

std::sort 1.33s 5.56s

pdqsort 1.33s 2.81s

blqsort (single threaded) 0.93s 0.66 1.98s

For a fair comparison, the single-threaded version of blqs was used here. On an M1, the threaded versions are another factor of 3 to 4 faster.…