あまり計算量の証明について日本語の資料がなかったので、証明部分も含めてイントロソートについてまとめてみます。
イントロソートとは、クイックソートの改良版として1997年にDavid Musserによって提案されたソートアルゴリズムです。
以降ソート対象の配列の要素数を$n$とします。
クイックソートは期待実行時間が$\Theta(n\log n)$かつ定数部分が極めて小さいため実用上は最も高速であるとされており、さらにその場でソートできる1ため、なるべく使いたい（＝標準ソートとして採用したい）アルゴリズムです。
しかしクイックソートはひとつ欠点があります。それは最悪計算量です。
最悪計算量としては$O(n^2)$となってしまうため、Dos攻撃に利用できるなどセキュリティ上の懸念があります。
そこでクイックソートの実用上優れている点を享受しつつ、最悪計算量は落とすことを目的として提案されたのがイントロソート（Introspective Sort）です。
初めはクイックソートを行い、再帰の深さが要素数の対数$O (\log n)$を超えた後はヒープソートに切り替えるというシンプルなアルゴリズムです。
本題ではないので仔細は省きます。Wikiの疑似コードがわかりやすいと思います。
まずはクイックソート部分からです。
ある深さの再帰での比較回数は合計してもは高々$n$回です。また再帰の深さは$O(\log n)$となるように打ち切っているので、クイックソート部分の計算量は$O(n \log n)$であることがわかります。
またヒープソート部分について、ヒープソートで切り替えた時点で要素$k$個に分割されているとすると、各分割の要素数は$n_1, n_2, \cdots, n_k$のように表せます。
各分割$i (i = 1, 2, \cdots, k)$での計算量はヒープソートの性質より$O(n_i \log n_i)$であり、$n_i$の和は$n$であることに注意すると、計算量の和をとっても$O(n \log n)$です。
以上で
であることがわかったので、イントロソートの計算量も$O (n \log n)$です。
数式や下限の証明など詳細は割愛します。気になる方は元論文を読んでみてください。
配列の中で再配置して実行し、配列外の場所に置かれる要素が高々定数個であること。in-placeともいう。 ↩