Re: sorting in C

[Andrew Cohen <acohen@ust.hk>]

Turns out porting the cpython version of timsort was easier than I
expected :) There remain a few things to do but mostly finished.

Here are some (slightly) improved benchmarks (orig = original mergesort;
vec = convert to vector and use existing vector sort; tim = convert to
vector and use timsort).  The numbers are microseconds.

Key: all lists are length=1000; in the first two rows the lists are
blocks of sorted sublists of length 100 and 10 respectively; next is a
list with the ith element= (logxor i 1); then a constant list, random
list, a sorted list with 3 random elements swapping position, reverse
sorted list, and finally a sorted list.

|                                    | orig | vec | tim |
|------------------------------------+------+-----+-----|
| (make-block-list 1000 100)         |  157 | 118 |  78 |
| (make-block-list 1000 10)          |  200 | 153 | 160 |
| (make-evil-list 1000)              |  117 |  82 |  89 |
| (make-constant-list 1000)          |  107 |  75 |  17 |
| (make-random-list 1000)            |  211 | 164 | 167 |
| (make-swapped-list 1000 3)         |  123 |  89 |  23 |
| (nreverse (make-sorted-list 1000)) |  109 |  77 |  17 |
| (make-sorted-list 1000)            |  107 |  73 |  17 |

You can see that its always significantly better than the existing list
mergesort. Its comparable to the existing vector sort for the more
random cases, and hugely better on the more sorted cases. It is exactly
the cpython algorithm so no surprise that it tracks the benchmarks that
others have performed on the cpython code.

I have a few questions that I'll ask in a subsequent post.

Best,
Andy

-- 
Andrew Cohen