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.