さて、Mergesortはシータ（NlogN）の最悪の時間を持っていますが、そのオーバーヘッドは高く、マージが行われた再帰ツリーの最下部付近に現れます。誰かが、サイズがKに達した時点で再帰を停止し、その時点で挿入ソートに切り替えるよう提案しました。この修正された反復関係の実行時間がシータ（NK + Nlog（N/k））であることを証明する必要がありますか？私はこの問題に近づく方法については空白にしています。最適化されたmergesortの証明実行時間はtheta（NK + Nlog（N/K））ですか？
この問題の再帰関係を見てみるとよいでしょう。私はそれがこのようになります典型的なマージソートのために想像：あなたは半分の大きさの2つの部分問題に問題を分割して、Nの仕事（マージ）を実行している
T(N) = 2 * T(N/2) + N
すなわち。私たちは、一定の時間がかかる基本ケースを持っています。
我々が持っている木としてこれをモデル化：
T(N) = N -> T(N/2)
-> T(N/2)
= N -> (N/2) -> T(N/4)
-> T(N/4)
-> (N/2) -> T(N/4)
-> T(N/4)
これには、本当に私たちはちょうどそれがどのようになるの深い参照してくださいする必要があり
T(N) = N + 2N/2 + 4N/4 + ...
= N + N + N ...
の拡張を提供します。我々は、iレベルがサブ問題N/2^iのサイズで動作することを知っています。だから、私たちのリーフノード（T(1)）N/2^L = 1場所レベルLに発生します。
N/2^L = 1
N = 2^L
log N = log(2^L)
log N = L
だから、私たちのランタイムがN log Nです。
ここで、挿入ソートを紹介します。私たちのツリーは言い換えれば、この
T(N) = ... -> I(K)
-> I(K)
...x N/K
ようになります、我々はいくつかのレベルでLはサイズKのN/K挿入ソートの問題を解決する必要があります。挿入ソートの最悪実行時間はK^2です。だから我々は、合計でこれだけの作品を持っている葉で：前に説明したように
(N/K) * I(K)
= (N/K) * K * K
= N * K
しかし、我々はまた、ツリーのレベルごとNの費用で、同様に行うために合併の束を持っています。バック私たちの以前の方法になるだろう、のは（私たちはサイズKの部分問題に到達する前にレベルの数、したがって、挿入に切り替える）Lを見つけてみましょう：合計で
N/2^L = K
N/K = 2^L
L = log (N/K)
だから我々は
O(N) = N * K + N * log (N/K)
それがされています持っていますあまりにも長い間、私はあなたに証明のスケッチを与えるアルゴリズムを取ったが、それはあなたのニューロンを発射させるはずです。