ティムソート
2番目が小さい場合、マージは最後から始まります。この最適化により、必要な要素の移動数、実行時間、および一般的な場合の一時的なスペースのオーバーヘッドが削減されます。
例:2つの並び[1、2、3、6、10]と[4、5、7、9、12、14、17]をマージする必要があります。両方の並びはすでに個別にソートされていることに注意してください。 2番目の並びの最小要素は4であり、その順序を維持するために、最初の並びの4番目の位置に追加する必要があります(並びの最初の位置が1であると想定)。最初の並びの最大要素は10であり、順序を維持するために2番目の並びの5番目の位置に追加する必要があります。したがって、[1、2、3]と[12、14、17]はすでに最終位置にあり、要素の移動が必要な並びは[6、10]と[4、5、7、9]です。この知識があれば、5ではなくサイズ2の一時バッファを割り当てるだけで済みます。
ティムソート (Timsort) は2002年にPythonで TimPetersによって実装された安定ソートアルゴリズムの一種。マージソートと挿入ソートから派生しており、実世界の多くの種類のデータで適切に機能するように設計されている。
このアルゴリズムは、すでに整列されているデータのサブシーケンスを見つけ、それらを使用して残りをより効率的にソートします。これは、特定の基準が満たされるまで並びをマージすることによって行われます。 ティムソートは、バージョン2.3以降のPythonの標準的な並べ替えアルゴリズムで、Java SE 7 、Androidプラットフォーム 、GNU Octave 、V8 、Swift 、Rust においても非プリミティブ型の配列のソートアルゴリズムとして採用されています。
ティムソートは、PeterMcIlroyの1993年の論文「Optimistic Sorting and Information Theoretic Complexity」の手法を使用しています。