O(nlogn)より速いソートが存在しないこと - オタクof数理の共同ブログ

こんにちは。zalgo（@zalgo3）です。

クイックソートとかヒープソートが $O(n\log n)$ で行えることは有名ですね。
実はソートについては次の定理が成り立ちます。

定理
長さ $n$ の列のソートの計算量の下界は $\Omega (n\log n)$ である。

証明
ソートは、２つの要素を比較し、列を並び替える操作を繰り返すことにより行われる。
この流れを二分木で表す（比較の結果に応じて分岐していく）。
すると、葉が最終的な列を表している。
任意のソートが行えるためには、葉の数は $n!$ 個必要である。
$\therefore$ 二分木の高さを $h$ とすると、
$\displaystyle h\geq \log_2 n!$
$h=\Omega (n\log n)$ であることを示せば良い。
Landauの記号の定義から、 $n$ は十分大きいとみなしてよい。
Stirlingの公式
$n!\simeq \sqrt{2\pi n}\left( \frac{n}{\mathrm{e}}\right)^n$
より、
$\log_2 n!=\Omega (n\log n)$

有名な証明なので知ってても損はないと思います！