Python の組み込み sort() メソッドの内部動作を調べる

Python の組み込み sort() メソッドは、データ構造を昇順に整理します。 Timsort として知られるこのメソッドの背後にあるアルゴリズムは、小さな配列の挿入ソートの効率性と、大きな配列のマージ ソートの安定性を組み合わせたハイブリッド ソート アルゴリズムです。

Timsort: ハイブリッド アプローチ

Timsort アルゴリズムは、まず入力配列を所定のサイズの小さなサブ配列に分割することによって機能します。これらのサブ配列は、挿入ソートを使用してソートされます。これは、小さな配列では非常に効率的です。

サブ配列がソートされると、アルゴリズムは、マージ ソート アルゴリズムの修正バージョンを使用してそれらをマージします。このアプローチにより、並べ替えの安定性が保証されます。つまり、元の配列内の等しい要素が並べ替えられた出力でも相対的な順序を保持します。

実装の探索

ソース コードsort() メソッドは C で使用でき、Python インタープリター自体で見つけることができます。コードは非常に広範ですが、その本質はソート プロセスを処理する関数 timlsort にあります。

timlsort 関数は入力配列を反復処理して、所定のサイズのサブ配列を作成します。次に、マージ関数を呼び出して、配列全体がソートされるまで、ソートされたサブ配列をより大きなグループに結合します。

追加リソース

Timsort アルゴリズムの詳細な説明とその実装については、次のリソースを参照してください:

• Python 実装:
• テキストによる説明:
• Joshua Bloch による Java 実装: