Re: [boost] [review] Last day for formal review for Sort library

Subject: Re: [boost] [review] Last day for formal review for Sort library
From: Paul A. Bristow (pbristow_at_[hidden])
Date: 2014-11-20 05:26:46

> -----Original Message-----
> From: Boost [mailto:boost-bounces_at_[hidden]] On Behalf Of Steven Ross
> Sent: 19 November 2014 23:18
> To: boost_at_[hidden]
> 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
[phone]