Timsort

Timsortを, python 3.4.3のコードを1行1行追いながら移植.
GitHub-Timsort

以下のJava7の実装では例外が発生するケースでテストしてみた.
http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/

コードがかなり複雑. gallop_rightのあたりの理解がさっぱり.
ランダムデータではIntrosortの方が,
ソートされた部分が多いほどTimsortの方が速い,
とのことであるが, 実測はどうだろうか.

適材適所ではあるので, ライブラリに
アルゴリズムが複数あって困ることはない.

ついでにGoogle CodeからGitHubへ移行.
Exportボタンを押すだけで終了したので,
何か書くことも無し.