ソート番号

数学とコンピュータ サイエンスにおいて、ソート数とは、比較ソートアルゴリズムの分析のために1950 年にHugo Steinhausによって導入された一連の数です。これらの数は、バイナリ挿入ソートとマージ ソートの両方で使用される比較の最悪ケースの数を示します。ただし、比較回数がより少ないアルゴリズムも存在します。

番目のソート番号は式^{[1]で与えられる。}${\displaystyle n}$

${\displaystyle \displaystyle n\lceil \log _{2}n\rceil -2^{\lceil \log _{2}n\rceil }+1.}$

この式で与えられる数列（ から始まる）は ${\displaystyle n=1}$

同じ数列は再帰関係^[2]からも得られる。

${\displaystyle A(n)=A{\bigl (}\lfloor n/2\rfloor {\bigr )}+A{\bigl (}\lceil n/2\rceil {\bigr )}+n-1}$。

これは2-正規列の例である。^[2]

漸近的に、番目のソート番号の値は、と最も近い2の累乗 との比に応じて、およそ と の間で変動します。^[1]${\displaystyle n}$${\displaystyle n\log _{2}n-n}$${\displaystyle n\log _{2}n-0.915n,}$${\displaystyle n}$

1950年、ヒューゴ・スタインハウスは、これらの数字がバイナリ挿入ソートで使用される比較の数を数えていることに着目し、任意の比較ソートを使用して項目をソートするために必要な比較の最小数を与えると（誤って）推測しました。この推測は1959年にLRフォード・ジュニアとセルマー・M・ジョンソンによって反証されました。彼らは、より少ない比較を使用する別のソートアルゴリズム、フォード・ジョンソンマージ挿入ソートを発見しました。^[1]${\displaystyle n}$

同じソート番号のシーケンスは、マージソートでアイテムをソートするために使用する比較の最悪ケースの数も示します。^[2]${\displaystyle n}$

ソート番号（1つシフトしたもの）は、階層化された順列の最短のスーパーパターンのサイズも与えます。^[3]