ティムソート（Timsort）とは？仕組み・minrun・ガロップから実装上の最適化まで徹底解説
エバープレイ編集部ティムソートとは — 概要
ティムソート（Timsort）は、実運用データに対して高い性能を発揮する比較ソートのアルゴリズムです。Tim Peters が 2002 年に考案し、当初は Python の list.sort（および組み込み sorted）用に実装されました。マージソートと挿入ソートの長所を組み合わせ、配列の「既に整列されている部分（run）」を見つけてそれらを効率よく結合することで、平均的および実世界の入力に対して非常に高速かつ安定（stable）に動作します。現在では CPython の標準ソート実装のほか、Java（オブジェクト配列）や多くのライブラリ実装に採用されています。
設計思想と特徴
- ハイブリッド性：小さな区間には挿入ソート（binary insertion sort）を用い、区間同士の結合にはマージ手法を用いる。
- 適応性（adaptive）：入力中に既に存在する増加・減少の連続区間（run）を活用するため、ほぼ整列済みのデータに対しては O(n) に近い性能を出す。
- 安定性：等しい要素の相対順序を保つ安定ソートである。
- 最悪計算量：比較回数は O(n log n)（理論的最悪）であり、一般の比較ソートの下限に合致する。
- 追加領域：マージ処理のために補助配列を使用するため、追加のメモリが必要（実装により O(n) に近い補助領域を使う場合が多い）。
アルゴリズムの流れ（高レベル）
ティムソートは大きく次のステップから成ります。
- 入力配列を左から走査し、単調増加（または単調減少を検出して反転）の「run」を見つける。
- 短い run はバイナリ挿入ソートで長さをある閾値（minrun）まで延長する。
- 検出・延長した run をスタックに積み、スタック上の run 長さに関する不変条件（invariant）を満たすように部分的にマージする。
- 最終的にスタック上に残った run を順にマージして全体を整列する。
run と minrun
「run」は、配列中の連続する既に整列された区間です（増加する run を基本にするが、減少する run が見つかるとそれを逆順にして増加に揃える）。ティムソートはこれらの run を単位として処理します。
短すぎる run はそのまま置いておくとマージの効率が落ちるため、アルゴリズムは run を「minrun」と呼ばれる最小長さ以上に拡張します。拡張には挿入ソート（実装上はバイナリ挿入ソート）が用いられ、短い run を高速にソートしてからスタックに積みます。
minrun の計算は実装（CPython／OpenJDK の TimSort 等）で次のように行われることが多く、minrun は通常 32〜64 の間の値に決定されます（入力長 n に依存）。具体的には n を右シフトし、切り捨てられる最下位ビットを r に集めて最後に n + r を minrun とする方式です。こうすることで minrun が 32〜64 の範囲に収まるよう調整されます。
スタックとマージ不変条件（invariants）
検出して拡張した run は順次スタックに積まれます。単に最後に見つけた run を逐次マージしていくと最悪時に性能が悪化するため、スタック上の run 長みに対して一定の不変条件を維持することでバランスの良いマージを行います。
典型的な実装（CPython, OpenJDK に近い実装）で用いられる条件は以下のようなものです（スタック上の run 長を ..., X, Y, Z とし、Z が一番上）：
- len(X) > len(Y) + len(Z)
- len(Y) > len(Z)
実装上はこれらを直接満たすように保つのではなく、スタックに新たな run を push した後に以下のような判定を行い必要ならマージを実行します（擬似的）:
- もしスタックに 3 個以上の run があり、len[-3] <= len[-2] + len[-1] なら、len[-3] と len[-2] をマージするか、len[-2] と len[-1] をマージするかを選択してマージする。
- もしスタックに 2 個以上の run があり、len[-2] <= len[-1] なら、len[-2] と len[-1] をマージする。
こうしたルールにより、マージのバランスがとられ、最悪時でも O(n log n) の振る舞いが保証されます。どのペアを優先してマージするかは実装細部に依存しますが、基本理念は「非常に小さい run が大きな run に一度に飲み込まれるのを防ぐ」ことです。
ガロップモード（Galloping / Exponential search）
マージ中に、片方の run から連続して多数の要素が勝ち続ける（取り出され続ける）場合、通常の一元素ずつ比較して取り出す方法は非効率になります。ティムソートではこの状況を検知すると「ガロップモード」に切り替えます。ガロップモードでは指数的探索（galloping / exponential search）を用いて、一度にまとめてバルク移動できる範囲を見つけ、より効率的に結合します。
このときのしきい値（何回連続で勝てばガロップに切り替えるか）は実装で調整可能で、CPython と OpenJDK の実装では初期値が 7（min_gallop = 7）に設定されています。ガロップモードの活用は、特に偏った要素分布や既部分整列状態で有効に働きます。
計算量とメモリ
- 最悪時間計算量：O(n log n)
- 平均・実用上：ほぼ O(n log n)、しかしほとんど整列済みの場合は O(n) に近い振る舞いを示す
- 追加メモリ：マージ用の補助バッファを使うため O(n) 程度（実装により最適化される）。
ティムソートは比較回数とデータ移動を実用的に減らす設計になっているため、多くの現実的なワークロードで非常に高速です。ただし、メモリ使用量や分岐の多さから、例えばプリミティブ型の配列ソートでは別のアルゴリズム（たとえば Java の双基準クイックソート実装やデュアルピボットクイックソート）が好まれる場合があります（Java はプリミティブ型専用に別実装を持つ）。
実装上の注意点と最適化
- バイナリ挿入ソートで run を延長する際、比較回数を減らすためにバイナリサーチを用いる。
- ガロップモードへの頻繁な切り替えは逆効果になることがあるため、min_gallop を動的に調整する仕組み（勝敗の推移を見て閾値を上下させる）が入っている。
- メモリ割当てを繰り返すと性能が落ちるため、一時バッファを再利用する実装が望ましい。
- 安定性を保つために、等しいキー同士の順序を崩さないマージを行う。
採用例と歴史的背景
ティムソートは Tim Peters によって 2002 年に開発され、Python 2.3 のリリース以降 Python の標準ソートとして採用されました（list.sort / sorted）。以降、多くの実装や言語で採用・影響を与えています。代表的な例：
- CPython の標準 list.sort（および組み込み sorted）は TimSort を採用している。
- Java（OpenJDK）では、Object[] のソートに TimSort ベースの手法が採用されている（プリミティブ型用には別の最適化されたアルゴリズムが使われる）。
- その他、多くのライブラリ実装や言語実装で、実データに強い安定ソートとして採用されている。
TimSort の登場以前にも「実用的な高速ソート」の研究は進められていましたが、TimSort は「既整列性」を明示的に活用する点と、実装上の実用配慮（ガロップ、minrun、スタック不変条件など）の組合せで、非常に実用的なソート実装となっています。
ティムソートが向いているケースと向かないケース
向いているケース：
- ほとんど整列済みのデータや、局所的に整列されたデータ（セグメント単位で並んでいる）が多い。
- 安定性が求められる場合（等しいキーの相対順序を保持したい）。
- 一般的なオブジェクト配列など、比較コストがそれほど小さくないケース。
向かない（または注意が必要）なケース：
- 極端にメモリ制約が厳しい環境では、補助配列の使用が問題になる場合がある。
- プリミティブの大量データを扱う際、CPU キャッシュや低レベルの最適化を活かすために専用アルゴリズム（例：デュアルピボットクイックソートなど）が速い場合がある。
実装を読む・触る
実際の実装ソースを読むと細かなチューニングが多数盛り込まれていることがわかります。CPython の listsort.txt（Tim Peters の設計説明）や、OpenJDK の TimSort 実装は特に学習に適しています。実装上はガロップの閾値や minrun の決め方、スタック操作の詳細など、性能に影響するパラメータが整備されています。
まとめ
ティムソートは「既整列性」を積極的に利用することで、実世界のデータに対して非常に効率よく動作する安定ソートです。マージソートの安定性と挿入ソートの短区間高速性を組み合わせ、ガロップやスタック不変条件などの実践的な最適化を取り入れることで、Python をはじめ多くの環境で標準ソートアルゴリズムとして採用されています。理論的に最悪 O(n log n) を保ちつつ、実データでの高速化を重視する場面で強力な選択肢となります。
