Re: sorting in C

[Andrew Cohen]

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

[...]

    EZ> But for showing the performance, the license is not important,
    EZ> is it?

OK, I couldn't resist :) Here are some simple numbers for timsort. These
are in microseconds, and there is no special case of small lists.  I
have lots more data but this should be enough to whet your appetite.
Note that "worst" isn't worst case for timsort (it was only worst case
for insertion sort, which isn't used in these benchmarks). For longer
random lists its comparable to the existing /vector/ sort routine, which
as I have said is 30% faster than the recursive merge used for lists.
For partially sorted lists its very, very fast.

|          |   oldsort |   timsort |
|----------+-----------+-----------|
| s65      |     6.001 |     1.808 |
| r65      |     6.626 |     2.982 |
| rand65   |    11.062 |    10.371 |
| worst65  |     8.524 |     6.751 |
| rand100k | 33722.263 | 30913.107 |

-- 
Andrew Cohen