fast, clean, C, timsort implementation?

Question

Does anyone know of a clean C/C++ implementation of timsort?

The Python sources contain a description and code for the original timsort, but it is understandably full of python-specific calls.

Thanks!

Answer 1

http://www.google.com/codesearch/p?hl=en#-wKRNbYkeKI/pub/FreeBSD/distfiles/cdo-1.0.2.tar.gz%7C2Bzv0TJ6z70/cdo-1.0.2/src/Timsort.c&q=timsort%20lang:c

is it a timsort you wanted?

And other variant (more likely you wanted this)

http://www.google.com/codesearch/p?hl=en#p1eHeX-3lSM/timsort.c&q=timsort%20lang:c&sa=N&cd=4&ct=rc

It is not complete, but it describe code a lot in post.txt

Answer 2

This implementation from Android isn't in C, but it's way easier to understand than the original that's on Python's SVN.

http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/TimSort.java?view=co

Hopefully it's relatively easy to translate to C code.

Answer 3

I wrote a fast, template-like version in C:

http://github.com/swenson/sort

It also includes a bunch of other sorting algorithms. Timsort seems to beat quick sort by 5% or so.