A C++ Quicksort Faster Than std:sort

BLQSORT is a general-purpose C++ quicksort presented as a faster alternative to std::sort, especially for large arrays of random or partly ordered data. Its development illustrates why basic quicksort needs safeguards: poor pivot choices can make sorted input take quadratic time, while a middle-element pivot helps with ordered data but can still be vulnerable to crafted inputs. Randomized pivot selection addresses that risk. The implementation also uses sorting networks for small partitions, where fixed sequences of compare-and-swap operations can outperform insertion sort, and emphasizes avoiding branch-heavy code when unpredictable conditions slow execution. The author notes that Hoare partitioning makes fewer comparisons and swaps than Lomuto partitioning, but may have less favorable cache behavior on modern processors.

Benchmarks sort 50 million random doubles compiled with optimization enabled. On an Apple M1, BLQSORT takes 0.68 seconds, compared with 1.33 for std::sort and 1.00 for an ipnsort port; on an Intel i5-9300H, the times are 1.32, 4.02, and 2.11 seconds, respectively. With 90%-sorted input, BLQSORT also leads: 0.72 seconds on the M1 and 1.41 on Intel, versus 1.25 and 1.84 for std::sort. These results support the claim that the implementation is particularly fast on the tested data and systems, though specialized SIMD sorts may beat it for small primitive types. The code is available under the MIT license, with C and multithreaded versions also offered.