Re: [boost] Proposed templated integer_sort

Subject: Re: [boost] Proposed templated integer_sort
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2009-01-14 17:27:57

Earlier I wrote:
> One of the things that your string sort does is to not compare 
> known-equal initial substrings.  Does anyone know if there is a variant 
> of a conventional sort (e.g. quicksort) that does this?

I've had a quick play and come up with this:

     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.

Phil.