§D2.9整列と比較回数の下界

証明.

繰り返しを抜けた時点では$i > p$または$j > q$です。$i > p$の場合、残っているのは$y_j, \dots, y_q$だけであり、主張 2.2.1 (3)によりこれらは$z$のどの要素よりも大きく、しかも昇順に並んでいます。したがって手順 3 でこれらを末尾へ加えた列は昇順であり、主張 2.2.1 (2)とあわせて、入力の全要素をちょうど一度ずつ含みます。$j > q$の場合も同様です。▨

証明. 量$\mu = (p - i + 1) + (q - j + 1)$を考えます。手順 2 の各回で$i$または$j$のちょうど一方が$1$増えるので、$\mu$はちょうど$1$減ります。また繰り返しの条件$i \le p$かつ$j \le q$のもとで$\mu \ge 2 > 0$です。$\mu$は非負の整数で毎回真に減るので、繰り返しは有限回で終わり、手順 3 は繰り返しを含まないので、手続き全体が停止します。

比較は手順 2 の各回でちょうど一回行われるので、比較の回数は繰り返しの回数に等しく、繰り返しの回数は$z$へ加えられた要素の個数に等しくなります。繰り返しを抜けた時点で$i > p$または$j > q$ですが、繰り返しの条件から、抜ける直前の回では$i \le p$かつ$j \le q$であり、増えるのは一方だけです。したがって抜けた時点でもう一方の列には少なくとも一つの要素が残っており、その要素は手順 3 で加えられます。すなわち手順 2 で$z$へ加えられた要素は$p + q - 1$個以下であり、比較の回数も$p + q - 1$以下です。▨

証明. 入力の長さ$n$についての累積帰納法（§D2.1 命題 1.2）で示します。

$n \le 1$のとき、長さ$0$または$1$の列は昇順に並んでいるので、手順 1 の出力は正しく、繰り返しも再帰も行わないので停止します。

$n \ge 2$とし、長さが$n$より小さいどの入力についても主張が成り立つと仮定します。$\lceil n/2 \rceil$と$\lfloor n/2 \rfloor$はどちらも$1$以上$n-1$以下なので、$L_1$と$L_2$への再帰は帰納法の仮定の範囲にあり、いずれも停止して、$L_1$と$L_2$の要素を昇順に並べた列を返します。補題 2.3により併合も停止するので、手続き全体が停止します。補題 2.2により、出力は二つの列の要素をちょうど一度ずつ含む昇順の列です。$L_1$と$L_2$の要素をあわせたものは$L$の要素にほかならないので、出力は$L$の要素を昇順に並べ替えた列です。▨

証明.定義 2.4の構造と補題 2.3から、$C(1) = 0$であり、$n \ge 2$について

が成り立ちます。この不等式のもとで主張を$n$についての累積帰納法で示します。

$n = 1$のときは$C(1) = 0 = 1 \cdot \lceil \log_2 1 \rceil$です。

$n \ge 2$とし、$n$より小さいすべての正の整数について主張が成り立つと仮定します。$k = \lceil \log_2 n \rceil$とおくと、$n \ge 2$より$k \ge 1$であり、$n \le 2^{k}$です。よって$\lceil n/2 \rceil \le 2^{k-1}$であり、$\lfloor n/2 \rfloor \le \lceil n/2 \rceil \le 2^{k-1}$なので、どちらについても$\lceil \log_2 (\cdot) \rceil \le k - 1$です。また$\lceil n/2 \rceil$と$\lfloor n/2 \rfloor$はどちらも$1$以上$n-1$以下なので、帰納法の仮定を適用することができ、

が得られます。▨

証明. 入力の長さ$n$についての累積帰納法で示します。$n \le 1$のときは定理 2.5の証明と同じです。

$n \ge 2$とし、長さが$n$より小さいどの入力についても主張が成り立つと仮定します。入力の要素は相異なるので、$a$以外の$n-1$個の要素はそれぞれ$L_{<}$と$L_{>}$のちょうど一方に入り、$|L_{<}| + |L_{>}| = n-1$です。したがって$|L_{<}|$と$|L_{>}|$はどちらも$n-1$以下、すなわち$n$より小さいので、帰納法の仮定を適用することができ、二つの再帰はいずれも停止して、それぞれの要素を昇順に並べた列を返します。手順 3 は繰り返しを含まないので、手続き全体が停止します。

出力が昇順であることを確かめます。$L_{<}$を整列した列のどの要素も$a$より小さく、$L_{>}$を整列した列のどの要素も$a$より大きいので、三つをこの順に並べた列は昇順です。また出力は$L_{<}$の要素、$a$、$L_{>}$の要素をちょうど一度ずつ含み、これは$L$の要素の全体にほかなりません。▨

証明. 1 を示します。 比較の回数の最大値を$W(n)$とすると、$W(1) = W(0) = 0$であり、$n \ge 2$について、手順 2 が$n-1$回の比較を行い、$|L_{<}| + |L_{>}| = n-1$であることから

が成り立ちます。$W(n) \le n(n-1)/2$を$n$についての累積帰納法で示します。$n \le 1$では両辺が$0$です。$n \ge 2$とし、$n$より小さいすべての場合に主張が成り立つとすると、$0 \le s \le n-1$に対して

です。右辺を展開して整理すると、$s$の関数として

となります。$s^{2} - (n-1)s = s\bigl(s - (n-1)\bigr)$は$0 \le s \le n-1$の範囲で$0$以下であり、端点$s = 0$と$s = n-1$で最大値$0$をとります。したがって右辺の最大値は$(n-1)(n-2)/2$です。よって

となります。

2 を示します。 入力がすでに昇順であるとき、先頭の要素は最小なので$L_{<}$は空、$L_{>}$は残りの$n-1$個からなり、しかも昇順のままです。したがって比較の回数を$R(n)$とすると$R(1) = 0$かつ$R(n) = R(n-1) + (n-1)$です。$R(n) = n(n-1)/2$が$n$についての単純帰納法で従います。実際、$R(1) = 0 = 1 \cdot 0 / 2$であり、$R(n) = (n-1)(n-2)/2 + (n-1) = n(n-1)/2$です。

3 を示します。 分割の操作は$n-1$回の比較と、それに伴う$\Theta(n)$の手数で行うことができ、仮定から二つの部分列の長さはどちらも$n/2$と定数の差しかありません。よって$T(n) = 2T(n/2) + \Theta(n)$が成り立ち、マスター定理（§D2.8 定理 3.1）の場合 2 により$T(n) = \Theta(n \log n)$です。▨

証明. まず、相異なる置換$\pi \ne \pi'$に対して$r(\pi) \ne r(\pi')$であることを示します。$r(\pi) = r(\pi')$と仮定すると、$\mathcal{A}$の動作は比較の結果の列だけで定まるので、$\mathcal{A}$は二つの入力に対して同じ並べ替えを出力します。しかし$\mathcal{A}$は正しい整列の手続きなので、大小関係が$\pi$で表される入力に対する正しい出力は$\pi$による並べ替えに限られ（定義 1.1）、$\pi'$についても同様です。$\pi \ne \pi'$なので二つの出力は異なり、矛盾します。

次に、各$r(\pi)$が決定木の葉であることを示します。$r(\pi)$が子をもつとすると、$r(\pi)0$または$r(\pi)1$が$T$に属し、それはある$\pi'$について$r(\pi')$の接頭辞です。すなわち$r(\pi)$は$r(\pi')$の真の接頭辞です。ところが定義 4.1により、手続きが停止するかどうかはそれまでの比較の結果の列だけで定まります。$\pi$に対しては比較の結果の列が$r(\pi)$になった時点で停止するので、$\pi'$に対しても、比較の結果の列が$r(\pi)$に一致した時点で停止し、$r(\pi') = r(\pi)$となります。これは$r(\pi)$が$r(\pi')$の真の接頭辞であることに反します。よって$r(\pi)$は葉です。

以上より、$[n]$の$n!$個の置換に対する$r(\pi)$は互いに相異なる葉を与えるので、葉の個数は$n!$以上です。▨

証明.$h$についての単純帰納法（§A3.10 定理 1.1）で示します。

$h = 0$のとき、木は根だけからなり、根は子をもたないので葉です。葉の個数は$1 = 2^{0}$です。

$h \ge 1$とし、高さが$h-1$以下の二分木について主張が成り立つと仮定します。高さ$h$の二分木$T$をとります。$h \ge 1$なので根は少なくとも一つの子をもち、根自身は葉ではありません。根の子は高々二つで、各子を根とする部分木の高さは$h-1$以下です。$T$の葉は、これらの部分木の葉をすべて集めたものに一致します。帰納法の仮定により各部分木の葉は$2^{h-1}$個以下なので、$T$の葉は$2 \cdot 2^{h-1} = 2^{h}$個以下です。▨

証明. 決定木の高さは$h$です。補題 4.3により葉の個数は$n!$以上であり、補題 4.4により葉の個数は$2^{h}$以下です。よって$n! \le 2^{h}$、すなわち$\log_2 (n!) \le h$です。$h$は整数なので、$\log_2 (n!)$以上の整数のうち最小のもの、すなわち$\lceil \log_2 (n!) \rceil$以上です。▨

証明.$n! \ge n^{n/2}$を示します。積$(n!)^{2} = \prod_{k=1}^{n} k \cdot \prod_{k=1}^{n} (n+1-k)$を、同じ$k$の項どうしでまとめると$(n!)^{2} = \prod_{k=1}^{n} k(n+1-k)$です。$1 \le k \le n$において

なので$k(n+1-k) \ge n$です。よって$(n!)^{2} \ge n^{n}$、すなわち$n! \ge n^{n/2}$です。両辺の$\log_2$をとると$\log_2 (n!) \ge \frac{n}{2}\log_2 n$であり、定理 4.5とあわせて$h \ge \frac{n}{2}\log_2 n$が得られます。▨