ティムソートは汎用ですか、それともPython固有ですか？

Question

  

Timsortは適応性があり、安定しており、   自然なマージソート。それは超自然的です   多くの種類の部分的なパフォーマンス   順序付き配列（lg（N！）未満   比較が必要で、わずか   N-1）、まだPythonの以前の   高度に調整されたsamplesortハイブリッド   ランダム配列。

timsort がCPythonの外部で使用されているのを見ましたか？理にかなっていますか

Answer 1

はい、CPythonの外部、具体的にはPython、一般的にはPythonを使用することはかなり理にかなっています。

現在、 Javaの＆quot; modifiedソートのマージ＆quot; timsortを使用すると、最初の結果は非常に良好です。

Answer 2

アルゴリズムは非常に一般的ですが、利点はむしろPython固有のものです。ほとんどのソートルーチンとは異なり、Pythonのlist.sort（timsortを使用するもの）が気にするのは、不必要な比較を回避することです。ポインターコピー）または追加のメモリを割り当てることさえあります（常にポインターの配列であり、オーバーヘッドはPython操作の平均オーバーヘッドに比べて小さいためです。）

同様の制約下にある場合は、適切かもしれません。しかし、比較が本当にそれほど高価である他のケースを見たことはありませんが、：-）

Answer 3

特に馴染みがないように見えますが、「スマート」です。マージソートは、ソフトウェアの広い世界では一般的です。

それが理にかなっているかどうかに関しては、それはあなたがソートしているものと、比較対メモリ割り当ての相対的なコストに依存します。最大2 * Nバイトの追加メモリを必要とするソートは、メモリに制約のある環境では適切な選択ではありません。

Answer 4

ウィキペディアで今すぐ回答：timsortは、AndroidからコピーしたJava 7で使用されます。

Answer 5

Timsortは現在Androidにもあります： http://www.kiwidoc.com/java/l/x/android/android/5/p/java.util/c/TimSort

Answer 6

リンクした説明は完全に一般的です。