ティムソート
配列R1とR2を個別にマージすると、配列から選択された連続する要素の数が保持されます。この数が最小ギャロッピングしきい値( min_gallop )に達すると、ティムソートは、その配列から多くの連続する要素がまだ選択されている可能性があると見なし、ギャロッピングモードに切り替えます。 R1がそれをトリガーする責任があると仮定しましょう。このモードでは、アルゴリズムは、配列R1の配列R2の次の要素xに対して、ギャロッピング検索とも呼ばれる指数検索を実行します。これは2つの段階で行われます。最初の段階では、xがで − 1、2 第2段階では、第1段階で見つかった範囲内の要素xの二分探索を実行します。ギャロッピングモードは、配列中の要素間の間隔のパターンにマージアルゴリズムを適応させる試みです。
ギャロッピングは必ずしも効率的ではありません。場合によっては、ギャロッピングモードでは、単純な線形探索よりも多くの比較が必要になります。