配列の中の既存の順序を拾う
Timsortは自然に昇順となっている区間(ラン。以下では連と呼びます)を見つけ、隣接する連を安定にマージする適応的な整列法です。厳密な降順の連は反転すれば昇順にできます。同値キーを含む区間まで単純に反転すると元の出現順が崩れるため、降順の検出条件にも安定性への配慮が必要です。短い連は挿入ソートなどで適切な長さへ拡張します。全体を最初から同じ長さの区間に機械的に分けるだけでなく、入力の持つ順序を利用する点が特徴です。
二つの連を安定にマージする
[1,4,7,2,3,8]は[1,4,7]と[2,3,8]という二つの昇順連として読めます。先頭同士を比べ、小さい側を取り出すと1、2、3、4、7、8になります。同じキーが両側にある場合には、元の位置が前だった左側のレコードを先に出すことで安定性を保ちます。実装では短い方の連を一時領域へコピーし、前向きか後ろ向きにマージすることもあります。その場合も同値キーの扱いは処理方向に応じて一貫させる必要があります。
連の長さと併合順序
長い整列済みの連がある入力では、比較やデータ移動を減らせます。例えば入力全体が一つの昇順連なら、それを認識する一巡で済みます。一方、併合を極端に偏った順に繰り返すと大きな連を何度も移動することになるため、連の長さを考えた併合方針が重要です。最悪時間O(n log n)、追加領域O(n)という一般的な評価と、連の構成に応じた適応的な費用を分けて説明します。常に要素数に比例する時間で終わる整列法ではありません。
実装の版と名称を混同しない
CPythonの公式資料は、連の発見や安定なマージの仕組みに加えて、併合方針の変更も説明しています。現在の実装を調べるときは、古いTimsortのスタック規則がそのまま使われていると決めつけず、Powersortを含む採用版の方針を確かめます。比較が一方に偏るときにまとめて範囲を取り込むgallopingも、実装上の工夫です。同値キー、逆順の連、複数の短い連を試し、安定性、比較関数、作業領域の確保失敗をそれぞれ検証します。