マージソートのパフォーマンス

void main(void)
{
 //システム時間を計る計測器（クロック数で計算）
 B_Counter* sys_counter = new B_Counter();
 
 //配列を用意する
 int x[MAX_DATA];
 for(int i = 0; i < MAX_DATA; i ++){
  x[i] = (int)rand();
 } 

 //カウンター開始
 sys_counter->Counter_Start();
 
 //ソート開始
 merge_sort(x, 0, MAX_DATA-1);
 
 //カウンター終了
 sys_counter->Counter_End();
 
 //時間出力
 printf("%f \n", sys_counter->Get_Time());


 int c[MAX_DATA];

 for(int i = 0; i < MAX_DATA; i ++){
  c[i] = (int)rand();
 }

 sys_counter->Counter_Start();

 //一番単純なソートシステム
 for(int i = 0; i < MAX_DATA - 1; i ++){
  for(int a = i+1; a < MAX_DATA; a ++){
   if(c[i] > c[a]){
    int data = c[i];
    c[i] = c[a];
    c[a] = data;
   }
  }
 }
 sys_counter->Counter_End();

 printf("\n");
 
 printf("%f \n", sys_counter->Get_Time());
}

上記のようなソースでソートアルゴリズムをテストしてみました。

使っているアルゴリズムは二つで
１．マージソート。
２．アルゴリズムでも何でもない単純比較ソート。

その結果は・・・

・配列を２０個用意した場合
マージソート : 0.008979
単純ソート : 0.004489

２０個ソートしているのに何でここまで時間がかかるんだよって疑問を持ってる方もいらっしゃると思いますが、
そこんとこはおいといて時間をご覧ください。

なぜかマージソートのほうが時間がかかっています。
この時点では・・・マージソートって効率悪いなーって思ってましたが、配列の個数を増やしてみたら・・・

・配列を２００個用意した場合
マージソート : 0.085299
単純ソート : 0.300150

200個ソートした時点でかなりの差が見られました。
明らかにマージソートのほうが速いですね。

・配列を２万個用意した場合
マージソート : 12.141984
単純ソート : 3484.902047

この時点ではもう相手にならないですねｗ
マージソートの特徴かもしれませんが、ソートする量によって時間も比例しますが、
大量のデータのソートに適してるという結果がみられました！

かなり有意義なスピード比べでしたねーｗ（知らなかったのは自分だけかもしれませんがｗ）