Grokking Timsort

Question

Timsortというブロックに新しいソートがあります。これはPythonのlist.sortとして使用されており、今度はthe new Array.sort in Java 7になる予定です。

ありsome documentationとソートし、いくつかの低レベルの性能評価の高レベルのプロパティを記述するtiny Wikipedia articleだが、誰もがTimsortが何をしているかを説明するためにいくつかの擬似コードを提供できる場合、私は興味があった、正確に、かつ重要なものですジッピーなもの。 （ESPは。の論文、「楽観ソートと情報理論的複雑さ。」に関して）

（もrelated StackOverflow post参照。）

Answer 1

今削除されたブログ記事から関連部分を引用：Visualising Sorting Algorithms: Python's timsort

timsortのビジネス・エンドは、事前にソートされた要素の実行で動作するマージソートです。最終的なマージが可能な限り均衡していることを確認するために、最小ランレングスminrunが選択されます.64要素の場合、minrunは32になります。マージが始まる前に、ソートされた要素の既存の実行を検出するために、データを1回パスします。下降行程は、それらを逆転させるだけで処理されます。結果のランレングスがminrunより小さい場合は、挿入ソートを使用してminrunにブーストされます。重要な既存のランがないシャッフルされた配列では、このプロセスは上記の推測とまったく同じように見えます。差し込みソートを使ってminrun要素のブロックをあらかじめソートし、マージソートとマージします。

[...]

• timsortは下降の実行を見つけ、その場で実行を逆にします。これはポインタの配列で直接行われるので、私たちの立場から「瞬時に」見えます。
• 挿入のソートを使用してランの長さをminrunに引き上げました。
• 次のブロックの先頭で実行が検出されず、挿入ソートがブロック全体をソートするために使用されます。このブロックの下部にあるソートされた要素は特別に扱われないことに注意してください。timsortは、ブロックの中央で開始された実行をminrunに検出しません。
• 最後に、mergesortを使用してランをマージします。

Answer 2

それはいくつかの議論があるようで行ったとき、この変更はcore-libs mailing listを経て、そこの役に​​立つリンク。コードレビューの変更を伴うweb revとoriginal patchもあります。

コード内のコメントが言う：

実装上の注意：この実装は安定し、適応され、n個のLGよりもはるかに少ないが必要です
反復マージソート（n）を比較
入力配列があるとき入力配列が
の場合、伝統的なマージソートのパフォーマンスは
となります。入力配列がほぼソートされている場合、
の実装には約n回の比較が必要です。
一時的な記憶域要件は、ほぼ並べ替えの小定数と異なります。
入力配列はランダムに入力された入力のn/2オブジェクト参照
配列です。

実装は、その入力アレイに等しい上昇の利点と
降順を取り、同じ
入力配列の異なる部分に
上昇の利点と降順を取ることができます。 2つ以上のソートされた配列をマージするのに適しています。
単純に配列を連結し、結果の配列をソートします。
実装は、PythonのTim Petersのリストソート
TimSortから適応されました。これは、離散アルゴリズム、頁467-474、
1993年1月

埋葬に
第4回年次ACM-SIAMシンポジウムでピーター・マッキロイの「楽観
ソートと情報理論的複雑さ」からtechiquesを、使用していますvery useful link to the Python implementation detailsがあります。私はそれが始まるのに最適な場所だと考えています。その後、コードが続きます。信じられないほど高いレベルであるために、ソートされたデータの実行に気づき、ソート中にその構造を利用することによって、パフォーマンスが向上します。