the complexity was set to being O(n log n) comparisons on average. /
Generic programming is not bad, but it’s not enough. - Speed Is Found In The Minds of People (CppCon 2019 - Andrei) / r/cpp/

Sort covered:

• sorting small arrays - up to 15 elements
  • sorted hundreds of elements fast.
    • binary insertion sort is always worse than linear insertion sort - because of bad branch predictability (50% success) vs (87.5% for linear search).
    • branchless binary search is even slower - ?
    • Middle-out Insertion Sort - start in the middle - grow & sort on both end. - not significant difference
  • How about try silly things (since clever things have not work so far)?
    • stupid_small_sort - make_heap + insertion_sort - by doing more work
      • smoothsort, many comparisons still predictable
      • fewer swaps
    • remove comparison for heap / this what make it faster

Other take away:

• qsort is great for big arrays, terrible for small arrays (so in general rely on other sort for small arrays (see early stopping & THRESHOLD)
• ungarded_insertion_sort( begin +2, end); // can be ungarded because smallest element at then beginning of the array.
• micro algorithm
• what do you do to improve an algorithm that is implemented in a standard library, you look into the standard library.
• The pit of Hell: the Inner loop

see also:

• Miniselect: Practical and Generic Selection Algorithms - My favorite general sorting is pdqsort, it proves to be currently the best general sorting algorithm and it shows a significant boost over all standard sorts that are provided in C++.
• itCppCon19
• Changing std:sort at Google’s scale and beyond / HN - TL;DR; We are changing std::sort in LLVM’s libcxx.