ティムソート
ティムソート (Timsort) は2002年にPythonで TimPetersによって実装された安定ソートアルゴリズムの一種。マージソートと挿入ソートから派生しており、実世界の多くの種類のデータで適切に機能するように設計されている。
このアルゴリズムは、すでに整列されているデータのサブシーケンスを見つけ、それらを使用して残りをより効率的にソートします。これは、特定の基準が満たされるまで並びをマージすることによって行われます。 ティムソートは、バージョン2.3以降のPythonの標準的な並べ替えアルゴリズムで、Java SE 7 、Androidプラットフォーム 、GNU Octave 、V8 、Swift 、Rust においても非プリミティブ型の配列のソートアルゴリズムとして採用されています。
ティムソートは、PeterMcIlroyの1993年の論文「Optimistic Sorting and Information Theoretic Complexity」の手法を使用しています。