-----Original Message----- From: Boost [mailto:boost-bounces@lists.boost.org] On Behalf Of Steven Ross Sent: 19 November 2014 23:18 To: boost@lists.boost.org Subject: Re: [boost] [review] Last day for formal review for Sort library
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?
Put the bottom line first ;-)
But do include all of this (and more) in the docs - we are not short of space :-)
It is important that people realize just how complicated sort-speed is - if nothing else.
Paul
I thinks that’s a very good idea. The reason of existence of this code is “performance” so be as transparent as possible about that aspect. If people think this is to technical then they’ll skip the paragraph, but I I doubt it: typical users are likely looking for alternatives to std::sort because of performance. Knowing this will make it easier for developers to stress test performance benchmarks and know where to look for corner cases.