> Another problem is that I’m not sure what to do for data that I can’t sort. For example this algorithm can not sort a vector of std::sets
> Another problem is that right now there can only be one sorting behavior per type. You have to provide me with a sort key, and if you provide me with an integer, I will sort your data in increasing order. If you wanted it in decreasing order, there is currently no easy interface to do that.
Useful algorithm, but we already knew there are faster algorithms if we introduce additional requirements!
The O(n log n) lower bound is only for comparison based sorts. If you don't take a comparison function, but instead look at the internal structure, you can do better, but of course that depends on that internal structure and what order you want them in.
Would be more valid to compare to Boost's "spreadsort" which is similarly a hybrid radix sort algorithm (and also outperforms std::sort).
However, it might be possible if comparisons are not essential - e.g. radix sort is (with some assumptions) O(N)
Basically, how many elements do you have to move in a list of N elements to end up with one of the possible orderings
Most people would be fine with a hybrid radix sort for day to day use.
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 standard doesn't seem to say "or better" here, but I know that in other places it does (or least used to say something similar).
Note that this wouldn't be true if the standard said that it has to be Θ(n log n).
If something is O(1) it's also O(n) and O(n!), since it's an upper bound.
There the total number of elements are n and the average size of a partition is m. Then you need only apply any O(log(m)) algorithm to each partition to sort everything. That multiplies the time complexity by n/m. Then substitute n = m^c and the sort becomes O(n/c*log(n)) time. That gives you a factor of c speed up on what would otherwise be an O(nlogn) operation.
This trick is usable when you want to sort a B-Tree like structure where the data in each node is unsorted, but the nodes themselves are sorted. The file system hierarchy on a machine is like that. The default output of zfs list is also like that.
Unless it uses the same interface (aka call a comparator for each eval) it's apples to oranges. I also didn't see comparisons vs swaps enumerated, which matter for complex data structures or complex comparators.