Re: new module "mpsort" for faster sorting

[Jim Meyering]

Bruno Haible <address@hidden> wrote:
> Hello Paul,
>
>> Such a function can lead to faster execution
>> in some important cases, as I have verified using GNU 'ls' as a guinea pig.
>
> Does the speedup come from the use of the mergesort algorithm, or from
> avoiding a function call in the comparison function (with qsort, the
> pointer indirection must be done inside the comparison function; here it's
> done outside)?

Hi Bruno,

When sorting records larger than a pointer, reduced data movement is
likely to be the overriding factor: better use of cache.
I.e., setting up the array of pointers costs just O(N) time and memory,
but you save O(N log(N)) time in reduced data copying costs, because
mpsort is swapping only pointers, whereas qsort swaps the entire (larger)
records.

So, for small N and/or very small record size, there may be
a small run-time performance decrease, but for all other cases,
there should be an improvement.

Based on my minimal experience, I suspect that GNU sort will
end up using mpsort, too.