この記事は paiza Advent Calendar 2021 の1日目の記事です。

QuickSort(クイックソート)が、ちょっと話題になっているようですね。
平均計算量がO(n log n)というのは知識として知っている人もいると思いますが、なぜそうなるのかは証明を見る機会は少ないと思い、調べてみました。

Wikipediaには3つの証明が書かれていますが、ここでは一番簡単そうな方法、4分割法とでもいうでしょうか、を紹介します。

４分割法

クイックソートで配列を分割するとき、なるべく真ん中で分割する方が効率がよくなります。

分割時のピボット要素の順序が比較的真ん中の1/4〜3/4になる確率は50%です。これを幸運な場合と呼びます。

幸運な場合の中で最悪の場合は、配列が25%と75%に分割される場合です。分割のたびに、幸運が続き、この分割を繰り返すといつか分割された配列は一つになります。
つまり、分割回数をdとすると、幸運な場合の中で最悪の場合、以下の様になります。

$ 1 = n * (\frac{3}{4})^d $

変形すると

$ (\frac{4}{3})^d = n $

さらに変形して

$ d = log_{\frac{4}{3}} n $

これが、幸運な場合の最悪分割回数になります。

次に、残りの50%の不運な場合も考えます。不運な場合については、もう一回分割を行なってみます。それでも不運なら、もう一度分割、、、とするといつか幸運な場合が訪れます。平均すると、半分の確率で幸運は訪れるので、ずっと幸運な場合の平均2倍の分割回数になります。

つまり、$ 2 * log_{\frac{4}{3}} n $ となります。

分割回数ごとにn回の比較があるのでn倍になります。
これを、数字を消してO記法にすると、

$ O(n * log(n)) $

となります。

他の方法

漸化式を用いる方法、２分探索木と対応させる方法があるようです。