Re: sorting in C

[Andrew Cohen <acohen@ust.hk>]

>>>>> "EZ" == Eli Zaretskii <eliz@gnu.org> writes:

[...]

    EZ> The 5-fold slowdown is a pain, IMO.  Can we do better in the
    EZ> worst case?

Maybe, but probably not too much. That is the point of these
hybrids---they improve on some cases and do worse on others. Its a win
only if the real-world data favors the improved case.

I played around a bit more and lowering the length threshold to 40
might be a better compromise. I am working on a more thorough set of
tests first.

We can always dispense with the insertion sort bit (or set a very low
threshold) and just keep the vector routine. This is a consistent 30%
win across the board.

     >> And implementing TIMSORT will be even better---similar or better
    >> speedup for the best cases, and only marginal degradation of the
    >> worst.  But I think even this small change here is a win.

    EZ> Can we see the numbers?  This sounds like a net win to me.

Err, no? I have it all working but I'm using a C version of TIMSORT from
the web. I don't think the license is acceptable so it probably needs to
be written from scratch.  Shouldn't be that difficult (the algorithm
itself is well-documented) but I'm not sure how much time I have to
finish it.

Best,
Andy

-- 
Andrew Cohen