быстрый, чистый, C, timsort реализация?

Question

Кто-нибудь знает о чистой реализации timsort на C/C++?

Источники Python содержат description и code для исходного timsort, но вполне понятно, что для них требуются вызовы, специфичные для python.

Спасибо!

Answer 1

Я написал быстрый, шаблонный, как вариант в C:

http://github.com/swenson/sort

Она также включает в себя множество других алгоритмов сортировки. Кажется, что Timsort быстро разгоняется на 5% или около того.

Answer 2

Эта реализация с Android не в C, но это проще понять, чем оригинал, который находится на SVN Python.

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

Надеюсь, это относительно легко перевести в код C.

Answer 3

Я написал порт C++ с тем же интерфейсом, что и std :: sort(), с некоторыми бенчмарками и модульными тестами.

https://github.com/gfx/cpp-TimSort

Noe, что потому, что первоначальный реализация в OpenJDK и его лицензия GPL, лицензия моей реализации также GPL. Теперь он распространяется в лицензии MIT.