耗時(shí)
對(duì)比圖
公式中 n 為參與排序的個(gè)數(shù)，T(n) 為排序時(shí)間。
分析
n[0,10]
n[0,100]
n[0,1000]
由上面可以看出當(dāng) n 足夠大時(shí) n^2 會(huì)遠(yuǎn)遠(yuǎn)大于 nlogn ，由此可以得出當(dāng) C2 和 C3 差不多大時(shí)， nlogn 的效率會(huì)大于 n^2。
C2 != C3
當(dāng)C2 和 C3 不一樣時(shí)，由上圖還是可以得出上面的結(jié)論。
總結(jié)
我們可以從上面的分析得出一個(gè)結(jié)論，當(dāng) 需要排序的數(shù)足夠大時(shí)，歸并排序所需時(shí)間會(huì)遠(yuǎn)遠(yuǎn)小于插入排序所需要的時(shí)間。
