ソートの計算量と現実のプログラム

ソートアルゴリズムについての小ネタ。「ソートは迷わずクイックソート」と言われることがよくありますが[1]、場合によってはそれが最適ではないこともあるという話。ここではクイックソートと挿入ソートを比較します。 O-記法で書くとクイックソートの計算量はオーダーはO(n*log(n))で、単純な挿入ソートのそれはO(n^2)なので、見かけ上は前者のほうが速そうなのです。ただし、あくまでこの記法はnが無限に近づいたときの振舞いについて述べているだけなので、現実的なプログラムでは必ずしもクイックソートのほうが速いというわけではないです。 次のような仕様のプログラムで実際に両者の速度を比較してみましょう。 所定の下の整数要素を持つ配列をソートして、その所要時間出力する 第一引数(len): 要素数 第二引数(type): アルゴリズムの種類。'i'が挿入ソート。'q'がクイックソート。 この仕様を実装