マージソートの計算量について-O(n*logn) -マージソートの計算量はO(n*- C言語・C++・C# | 教えて!goo

ソートの計算量を議論するときは、通常「比較回数」を考えます。 (正確には、全ての計算の手間を数えあげる必要がありますが、通常 ・計算処理の中で「比較回数」が最も多くなる ・計算量(オーダー)では次数の低い項は無視できる ので、比較回数以外は考える必要がなくなります) ですので、マージソートの計算量を考える場合、「分割にかかる時間」ではなく、「(比較しながら行う)分割した部分列を統合していくのにかかる時間」だけを考えます。 で、マージソートにおいて分割した部分列を統合するのにかかる時間ですが、 たとえば、16の要素をマージソートする場合を例にあげると、 ・要素数が1の部分列を要素数が2の部分列に統合する時の比較回数は1回です。要素数が2の部分列は全部で8個あるので、比較回数は8回。 ・要素数が2の部分列を要素数が4の部分列に統合する時の比較回数は3回です。要素数が4の部分列は全部で4個あるの