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

Subject: Re: [boost] [review] Last day for formal review for Sort library
From: Steven Ross (spreadsort_at_[hidden])
Date: 2014-11-19 18:17:51

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 <thijs_at_[hidden]>
wrote:

>
> >
> > 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
>