Re: new module "mpsort" for faster sorting

[Paul Eggert]

Bruno Haible <address@hidden> writes:

> Does the major speedup come from the transition a) -> b), or from the
> transition b) -> c) ?

I didn't code those solutions separately, so I don't know.

I have written a replacement qsort that has the same API as standard
qsort, but uses mpsort internally.  It creates an array of pointers to
to the qsort elements, sorts the array, and then uses this info to
reshuffle the qsort array a la Knuth vol. 3 (2nd ed.) exercise 5.2-10
(with a few extra tricks).  For 'ls' my intuition that mpsort was the
better interface, due to less data overhead.  If I find the time I may
try the qsort replacement, but I think it'll be slower.

I was surprised to see Jim's report that the C locale made no
difference to him, compared to the en_US.UTF-8 locale.  This does not
match my results, as I recall.  Perhaps my UTF-8 strcoll is much
slower than his?  I'm using Debian stable, which has glibc 2.3.2.

I'd like to use mpsort in some other apps, too, of course.  'sort' is
an obvious candidate, but it already uses mergesort, so mpsort won't
be as big a win there I suspect.  fts is another candidate.