最小配列サイズ
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/08/18 08:12 UTC 版)
マージは、配列数が2の累乗に等しいか、それよりわずかに少ない場合に最も効率的であり、配列数が2の累乗よりわずかに多い場合は特に効率が低いため、ティムソートはminrunを設定して事前状態を確認します。 Minrunは、データのサイズをminrunで割った値が、2の累乗に等しいか、わずかに小さくなるように、32から64までの範囲から選択されます。最後のアルゴリズムは、配列のサイズの最上位6ビットを取得し、残りのビットのいずれかが設定されている場合は1を追加し、その結果をminrunとして使用します。このアルゴリズムは、64未満の配列を含むすべての配列で機能します。サイズ63以下の配列のために、このセットは、アレイ・サイズに等しいminrunとティムソートは挿入ソートに減少させます。
※この「最小配列サイズ」の解説は、「ティムソート」の解説の一部です。
「最小配列サイズ」を含む「ティムソート」の記事については、「ティムソート」の概要を参照ください。
- 最小配列サイズのページへのリンク