ソートアルゴリズムの計算量をくらべる

ソートアルゴリズムの計算量をまとめてみた。
ただし、マージソート・クイックソート・シェルソートあたりの優劣は、
ソート対象の個数や状態によって変動する。

例えばこの表からでも、

クイックソートはソート個数が一定以上になると、シェルソートより速くなりそう・・・

って事がわかる。

理由としては、「n log n」 vs 「n exp(1.25)」　はnによって大小関係が変わってくるから。
分岐点を探してみる。

n log n = n exp(1.25) ⇒ log n = n exp(1/4)

簡単のために、n = 2 exp(p)　とおくと、

p = 2 exp(p/4) ⇒ p exp(4) = 2 exp(p)

p = 16, n = 2 exp(16)

よって、n > 2の16乗（=65536） だと、n log n < n exp(1.25) となり、
オーダが逆転してしまう。