It's the better of O(N*log(N)) and O(N*((K/S)+S)), where K is the key
length in bits and S is the division factor (11 by default). Practically,
it ends up being a slightly better than constant speedup for integer_sort
and float_sort (that fluctuates based on the number of radix iterations
required) from N=10000 up until N gets close to 2^K when it starts
switching to bucketsort. For string_sort the speedup can be much more
dramatic for long keys (because it does O(N) comparisons, and string
comparisons take time proportional to the length of the key, making
comparison-based sort worst-case be O(N*log(N)*K/C), where C may be as high
as 64), but for shorter strings it has a speedup similar to integer_sort
and float_sort. Bottom line is: it's faster, but complicated to summarize.
Do you have a recommendation on how to summarize that better?
On Wed Nov 19 2014 at 8:36:13 AM Thijs (M.A.) van den Berg
The algorithm provides a sort that is faster than O(n*log(n)).
Is it possible to specify the O() of the algorithm instead of only claiming that it's faster? I've read 1.8x speed up compared to std::sort and that made me think that it's also O(n*log(n)), but with a different constant in front.
Specifying the exact O() is very informative, it tells you what to expect, how (the gap with std::sort) scales as a function of n.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/ mailman/listinfo.cgi/boost