[janwas]

Nice data point. This is also relevant beyond qsort vs std::sort. Some implementations of Quicksort use a 3-way partition to save work for skewed inputs (if the pivot occurs often, no need to recurse for all those values).

We have found that in the SIMD context, those two comparisons are expensive enough to make this no longer worthwhile. We instead special-case subarrays with one and two unique values, which can be about 4x as fast on real data vs uniform-random data.