> Yes, only your "10x" and "5-10x" numbers are overstated. OK. I am curious: what is the desired outcome for you in this discussion? If we are arguing whether

> Yes, only your "10x" and "5-10x" numbers are overstated. OK. I am curious: what is the desired outcome for you in this discussion? If we are arguing whether in some cases the speedup is 2x, I struggle to understand why anyone would use an 'only' 2x slower algorithm in a time-critical application. > they may [..] stick with heapsort to avoid the need to ship multiple binaries or add architecture detection. Huh, why would they do that? Calling VQSort() takes care of detection, and does not require multiple binaries. > All you need to correct this is one mention that you can do better than std::sort! By leaving this out, you instead reinforce the idea that it's a reasonable choice if you have to go scalar. When do people 'have to' go scalar? I suppose we can mention: "Note that other algorithms such as pdqsort can be about twice as fast as LLVM's std::sort as of 2023-06." > ipnsort has no explicit vectorization; some parts may be auto-vectorized Yes, Lukas mentioned it uses 128-bit SIMD so I am guessing it's via autovectorization. > I don't get why you dismiss radix sort so quickly, when your own research shows that an MSD/LSD hybrid > addresses the bandwidth problem well? Thanks for sharing that paper by the way, very elegant approach. :) Thanks. Unfortunately virtual memory is quite finite (the OS does not leave much for users, especially on Windows), so this approach is problematic for large arrays. Also, many of the use cases we see are 64 or even 128-bit elements, with varied and unpredictable distributions. Sure, radix sort can be suitable when there are smaller keys. > Comparison-based algorithms I consider most relevant at the moment are fluxsort/crumsort/quadsort .. > I keep notes at [2] Thanks. It's not clear to me how those ideas can interoperate with SIMD. For example, counting the range during partitioning turns out to be expensive, more so than it would be in scalar code (because fewer ports can run vector instructions than scalar instructions). An is-sorted check could be vectorized as you note, but it's not clear to me that that is a net win (extra cost if not alread sorted, and if it is, better to avoid the sort call in the first place). > I take issue with making blanket claims like "I'd consider AVX2 to be table stakes for any sorting algorithm" Here are some of my axioms: 1) all x86 CPUs we care about support AVX2 (which has been available since 10 years). 2) Lukas' measurements show that the fixed vqsort with AVX2 is the fastest starting at around 32 elements. (For less than that, I still struggle to understand how branchy insertion sorts can be worse than a single indirect branch to an AVX2 sorting network, and suspect this is due to remaining issues with measurement including lack of fences and an unusual attempt to 'poison' branch predictors/cache.) 3) It seems unlikely that anything using less SIMD hardware than vqsort (for example only SSE4) is going to outperform the AVX2 version. 4) we currently have no reason to use a slower sort. Do you disagree with any of those? I suppose there are some CPUs without AVX2, but it's an open question whether one would want to ship an entirely different algorithm for them.