シェルソート

シェルソートの実行時間（時間計算量）は、比較時に選ぶ間隔hによって大きく異なる。
前節の例ではhを2の累乗としたが、この場合、最悪計算量が${\displaystyle \mathrm {O} (n^{2})}$となってしまう。^[2]各周回で同じ位置の要素ばかりが比較交換されるため、h=1となった段階で「全体が大まかに整列されている」という仮定が成り立たなくなるためである。^[4]
より効率の良い（計算量の少ない）ソートを行うために、様々な間隔が提案されてきた。^[5]以下の表は、間隔を決定するための数列の例である。（${\displaystyle n}$は要素数）

数列の一般項 (k ≥ 1)	実際の数列	最悪計算時間	備考
${\displaystyle \left\lfloor {\frac {n}{2^{k}}}\right\rfloor }$	${\displaystyle \left\lfloor {\frac {n}{2}}\right\rfloor ,\left\lfloor {\frac {n}{4}}\right\rfloor ,\ldots ,1}$	${\displaystyle \mathrm {O} (n^{2})}$	ドナルド・シェルが最初に考案した数列。[2] ${\displaystyle n}$が2の累乗の時、上記動作例と同一。
${\displaystyle {\frac {3^{k}-1}{2}}}$　（${\displaystyle \left\lceil {\frac {n}{3}}\right\rceil }$以下）	${\displaystyle 1,4,13,40,121,\ldots }$	${\displaystyle \mathrm {O} \left(n^{\frac {3}{2}}\right){=}\mathrm {O} (n^{1.5})}$	ドナルド・クヌース、 1973[3] Pratt, 1971[6]に基づく。 平均計算時間は ${\displaystyle \mathrm {O} (n^{1.25})}$。[3][4]
${\displaystyle A_{0}{=}1,A_{k}{=}4^{k}+3\cdot 2^{k-1}+1}$	${\displaystyle 1,8,23,77,281,\ldots }$	${\displaystyle \mathrm {O} \left(n^{\frac {4}{3}}\right){=}\mathrm {O} (n^{1.33\ldots })}$	セッジウィック（英語版）, 1982[7]
${\displaystyle 2^{p}3^{q}}$ (${\displaystyle p\geq 0,q\geq 0}$)	${\displaystyle 1,2,3,4,6,8,9,12,\ldots }$	${\displaystyle \mathrm {O} \left(n\log ^{2}n\right)}$	Pratt, 1971[6] 既知の数列で最悪計算時間が最小となるもの。 間隔の狭め方が細かすぎるため、実用性は低い。[5]

これらの数列をソートの間隔として利用する際は、（要素数以内で）大きな数字から狭めていく。${\displaystyle {\frac {3^{k}-1}{2}}}$を使う場合、間隔hを121→40→13→4→1とする（hを3で整数除算していけばよい）。
様々な間隔の計算量について理論的に考察されているが、現状、どのような間隔が最適か（例えば、平均${\displaystyle \mathrm {O} (n\log n)}$時間となる数列があるか）は未解決問題である^[5]。