It is impossible for comparison-based sorts; sketch of proof: there are N! different arrangements. sorting is equivalent to figuring which one of those N! arrangements we are seeing. In the worst case, each binary comparison can reduce at most, 50% of the search space. Hence the worst case may need log_2(N!) comparisons, which is O(N log N)
However, it might be possible if comparisons are not essential - e.g. radix sort is (with some assumptions) O(N)
You only ever have to move every element once to get a (pre-known) permutation that represents the sorted list.
The problem is the information in a permutation (n! possible orderings) and one can only ever "throw away" half of them on every comparison, leading to log_2(n!) or nlog(n).
The STL sort uses operator<, so they can't implement it as radix sort without changing the interface. Maybe they could manage to special case it for some fundamental types, but most likely they'd need to add a new function, like for stable_sort.
This is correct. The C++ standard specifies that sort must have a big-O complexity of n log(n). This can be seen on pdf page 925 of this working draft from 2014 [1].
No, f = O(n log n) means that f doesn't grow significantly faster than n log n. That is true for f = n log n, but it's also true for f = n. The "or better" is implicit by using big-O.
Note that this wouldn't be true if the standard said that it has to be Θ(n log n).
STL does use hybrid sorting. It is usually implemented as an introsort, which begins with a quicksort and switches to heapsort based on the number of elements to be sorted.
I think the author just wanted to point out that "the" STL is not valid / accurate here; while the interface and behavior is defined, the implementation is afaik still vendor specific, e.g., the implementation in GCC may be different from the one provided by Microsoft.
Would be more valid to compare to Boost's "spreadsort" which is similarly a hybrid radix sort algorithm (and also outperforms std::sort).