Pythonでtimsortのminrunの長さを計算する方法

Question

私はPythonにはかなり新しく、timsortの再実装を書こうとしています。プログラムを書いている間、私はminrunの長さを取得する方法を取り組むことができませんでした。

minrun nはアレイの大きさ= N/minrun < = 2^N ：私は相談しているソースがminrunとして同定記載しています。

私は何をしようとしているのか理解していますが、私はPythonでどうすればいいのか分かりません。

すべてのアイデアやサンプルコードは非常に便利です、ありがとう！ウィキペディアtrimsort-articlepython timsortの実装に内蔵で

Answer 1

が記載されている：

Minrun範囲から選択される32〜64、包括minrunによって分割されたデータのサイズが、に等しいようなものであること、または2の累乗よりわずかに小さい。最終的なアルゴリズムは、配列のサイズの6つの最上位ビットをとり、残りのビットのいずれかが設定されている場合は1を加算し、その結果をminrunとして使用します。このアルゴリズムは、64より小さい配列を含むすべての配列に対して機能します。 63以下の配列の場合は、minrunを配列サイズと等しく設定し、Timsortは挿入ソートになります。

あなたはこのようにそれを行うことができます：他のtimsortの質問のために、それでなければなりません

minrun = length 
remaining_bits = length.bit_length() - 6 

if remaining_bits > 0: 
    minrun = length >> remaining_bits 
    mask = (1 << remaining_bits) - 1 
    if (length & mask) > 0: minrun += 1 

python timsortを見てみてください。