ティムソート
開発者が行ったベンチマークによると、ギャロッピングは、一方の配列の最初の要素がもう一方の配列の最初の7つの要素の1つではない場合にのみ有益です。これは、初期しきい値が7であることを意味します。ギャロッピングモードの欠点を回避するために、次の2つのアクションが実行されます。(1)ギャロッピングの効率がバイナリ検索よりも低いことが判明した場合、ギャロッピングモードは終了します。 (2)ギャロッピングの成功または失敗は、 min_gallopを調整するために使用されます。選択した要素が以前に要素を返したのと同じ配列からのものである場合、 min_gallopは1つ減り、ギャロッピングモードへの復帰を促します。それ以外の場合、値は1ずつ増加するため、ギャロッピングモードに戻ることはできません。ランダムデータの場合、 min_gallopの値が非常に大きくなるため、ギャロッピングモードが繰り返されることはありません。
ティムソートでは、ほとんどの実世界のデータに最初から存在する、連続した要素の自然な並びを利用するように設計されました。要素を収集しながらデータを順番に読み取っていくと同時に、それらの並びをスタックに配置します。スタックの最上位の並びがマージ基準に一致する場合は常に、それらはマージされます。これは、すべてのデータがトラバースされるまで続きます。次に、すべての並びが一度に2つマージされ、ソートされた並びは1つだけ残ります。 (従来のマージソートで行われるように)固定サイズのサブリストをマージする代わりに順序付けられた並びをマージする利点は、リスト全体をソートするために必要な比較の総数が減ることです。
各並びには、入力のサイズに基づく最小サイズがあり、アルゴリズムの開始時に定義されます。並びがこの最小並びサイズよりも小さい場合、挿入ソートを使用して、最小並びサイズに達するまで並びに要素を追加します。