PythonのSortは意外と効率的！

Posted at 2025-02-01

Timsort

Timsortは、マージソートと挿入ソートを組み合わせたソートアルゴリズムで、実際の使用では良好な効率を示します。Tim Petersが2002年にこのアルゴリズムを設計し、Pythonで使用されています（TimSortはPythonにおけるlist.sortのデフォルトの実装です）。このアルゴリズムは、ソート済みのブロック（データ内のパーティション）を見つけ、各パーティションをランと呼び、そして特定のルールに従ってこれらのランをマージします。Pythonは2.3バージョン以降、Timsortアルゴリズムをソートに使用しています。現在、Java SE7とAndroidもTimsortアルゴリズムを配列のソートに使用しています。

1. 操作

現実のデータの多くは通常、既にソートされている部分があり、Timsortはこの特徴を利用しています。Timsortの入力単位は個々の数字ではなく、パーティションです。各パーティションは「ラン」と呼ばれます（図1）。このランのシーケンスに対して、毎回1つのランを取り出してマージします。各マージは2つのランを1つのランに結合します。各ランは少なくとも2つの要素を持たなければなりません。Timsortは各ランを昇順と降順に分類します：ランが昇順の場合、ラン内の次の要素は前の要素以上でなければなりません（(a[lo] <= a[lo + 1] <= a[lo + 2] <=...)）；もしランが厳密に降順であれば、つまりラン内の前の要素が次の要素より大きければ（(a[lo] > a[lo + 1] > a[lo + 2] >...)）、ラン内の要素を反転させる必要があります（注：降順部分は「厳密に」降順でなければ反転しません。なぜなら、TimSortの重要な目標の1つは安定性を維持することであり、>=の場合に反転を行うと、アルゴリズムがもはや安定しなくなるからです）。

1.1 ランの最小長

ランはソート済みのパーティションです。ランは異なる長さを持つことがあり、Timsortはランの長さに基づいてソート戦略を選択します。例えば、ランの長さが特定の値より小さい場合、挿入ソートアルゴリズムがソートに選択されます。ランの最小長（minrun）は配列のサイズに依存します。配列要素の数が64未満の場合、ランの最小長は配列の長さであり、Timsortは挿入ソートアルゴリズムを使用してソートします。配列要素の数が63以上の場合、より大きな配列に対して、32から65の範囲からminrunと呼ばれる数が選択され、配列のサイズを最小ランサイズで割った値が2のべき乗と等しく、またはわずかに小さくなるようになります。これに対する最終的なアルゴリズムは、単に配列サイズの最上位6ビットを取り、残りのビットのいずれかがセットされていれば1を加え、その結果をminrunとして使用します。このアルゴリズムは、配列のサイズが64未満の場合も含め、すべてのケースで機能します。

1.2 ラン長の最適化

ラン長の最適化とは、ランの長さがminrunより小さい場合、そのようなランの長さがminrunの長さに達するように、配列から適切な要素を選択してランに挿入することを意味します。これにより、ほとんどのランの長さがバランスよくなり、その後のランのマージに役立ちます。

1.3 ランのマージ

ランを分割し、ラン長を最適化した後、次のステップはランをマージすることです。ランをマージする原則は、マージ手法において最高の効率を保証することです。Timsortアルゴリズムがランを見つけると、そのランの配列内の開始位置とランの長さをスタックに入れ、そしてスタックに先に入れられたランに基づいてそのランをマージするかどうかを決定します。Timsortはスタック内の非連続なランをマージしません（Timsortは非連続なランをマージしないのは、そうすると3つのすべてのランに共通する要素が中間のランに対して順序が乱れるからです）。

Timsortはスタック内の2つの連続するランをマージします。X、Y、Zをスタックのトップにある3つのランの長さとします（図2）。次の2つの条件が同時に満たされない場合、2つのランXとYはマージされ、次の2つの条件が同時に満たされるまでマージが続き、その後マージが終了します：

X>Y+Z
Y>Z

例えば：X<Y + Zの場合、X + Yは新しいランにマージされ、その後スタックにプッシュされます。上記のステップを繰り返し、2つの条件が同時に満たされるまで行います。マージが終了した後、Timsortは次のランを探し続け、見つけた後にそれをスタックにプッシュします。上記のステップを繰り返し、つまり、ランをスタックにプッシュするたびに、2つのランをマージする必要があるかどうかをチェックします。

1.4 ランのマージ手順

2つの隣接するランをマージするには一時的な記憶領域が必要で、一時的な記憶領域のサイズは2つのランのうち小さい方のランのサイズです。Timsortアルゴリズムはまず小さい方のランをこの一時的な記憶領域にコピーし、その後、元々2つのランを格納していた領域を使ってマージされたランを格納します。

単純なマージアルゴリズムは、単純な挿入アルゴリズムを使用して、要素を左から右または右から左に順番に比較し、その後2つのランをマージします。効率を向上させるため、Timsortは二分マージソートを使用します。まず、二分探索アルゴリズムを使用して挿入位置を見つけ、その後挿入します。

例えば、2つのランAとBをマージする場合、Aが小さい方のランであるとします。AとBはそれぞれ既にソートされているので、二分探索により、Bの最初の要素がAのどこに挿入されるべきかが見つかります（図4）。同様に、Aの最後の要素がBのどこに挿入されるべきかが見つかります。見つけた後、この要素以降のBの要素は比較する必要がありません（図5）。この種の探索は、乱数の場合にはあまり効率的ではないかもしれませんが、その他の場合には高い効率を示します。

1.5 ギャロッピングモデル

これは上記のランと同様のマージプロセスを説明しています。詳細はWikipediaのギャロッピングモデルを参照してください。

2. 性能

2.1 Timsortのコアプロセス

昇順部分のバックトラッキングと降順部分の性能劣化を減らすため、TimSortアルゴリズムは入力をその昇順と降順の特性に基づいてパーティション化します。ソートの入力単位は個々の数字ではなく、ブロック（パーティション）です。各パーティションはランと呼ばれます。これらのランシーケンスに対して、毎回1つのランを取り出し、ルールに従ってマージします。各マージは2つのランを1つのランに結合します。マージの結果はスタックに保存されます。すべてのランが消費されるまでマージを続け、その後、スタックに残っているランをマージし、1つのランだけが残るまで行います。このとき、この残ったランがソート結果です。

要約すると、Timsortアルゴリズムのプロセスは以下を含みます：

配列の長さが特定の値より小さい場合、直接二分挿入ソートアルゴリズムを使用する。
各ランを見つけ、スタックにプッシュする。
ルールに従ってランをマージする。

2.2 性能分析

情報学の理論によると、平均的なケースでは、比較ベースのソートはO(n log n)より速くなることはできません。Timsortアルゴリズムは、現実のデータの多くがいくつかのソート済みの領域を持つという事実を利用しているため、TimsortはO(n log n)より速いです。乱数の場合、利用できるソート済みの領域がなく、Timsortの時間計算量はlog(n!)になります。

Timsortと他の比較ベースのソートアルゴリズムの時間計算量の比較。

空間計算量の比較。

説明：
JSE 7はオブジェクトのソートにクイックソートを使用していません。なぜなら、クイックソートは不安定であり、Timsortは安定しているからです。

以下はJSE7のTimsort実装コードの1節で、Timsortの利点をよく説明しています：

A stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when running on partially sorted arrays, while offering performance comparable to a traditional mergesort when run on random arrays. Like all proper mergesorts, this sort is stable and runs O(n log n) time (worst case). In the worst case, this sort requires temporary storage space for n/2 object references; in the best case, it requires only a small constant amount of space.

一般的に言えば、Timsortは安定したアルゴリズムです。ソート対象の配列に既にソートされた数字がある場合、その時間計算量はn logn未満になります。他のマージソートと同様に、Timesrotは安定したソートアルゴリズムであり、最悪ケースの時間計算量はO(n log n)です。最悪の場合、Timsortアルゴリズムはn/2の一時的なスペースを必要とし、最良の場合、非常に少量の一時的な記憶領域のみを必要とします。