Re: [boost] Proposed templated integer_sort

Subject: Re: [boost] Proposed templated integer_sort
From: Steven Ross (spreadsort_at_[hidden])
Date: 2009-01-14 19:56:24

On Wed, Jan 14, 2009 at 2:27 PM, Phil Endecott <
spam_from_boost_dev_at_[hidden]> wrote:

>
>    http://svn.chezphil.org/libpbe/trunk/include/string_qsort.hh
>
> Of course the benefit depends on how many long common initial substrings
> there are.  Testing with the output of "find / -print" (i.e. the pathnames
> of every file on my system, which will have lots of common initial
> substrings) it is a bit slower than std::sort.  So the advantage of reducing
> the number of character comparisons [and that reduction is substantial] does
> not make up for the absence of whatever other cleverness std::sort does that
> I haven't replicated.  But I thought I'd post it anyway, in case anyone is
> interested or can see how it could be improved.
> <http://lists.boost.org/mailman/listinfo.cgi/boost>
>

Out of curiousity, did you test string_sort on the same example?
string_sort guarantees a reduction of at least 1 character in length every
iteration, which a comparison-based algorithm will not do.
Also, you should try insertion sort on small data sets (size 16 or so); that
should give your test algorithm a little speed boost.