-----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 --- Paul A. Bristow Prizet Farmhouse Kendal UK LA8 8AB +44 (0) 1539 561830