遅いマージソートです。
マージクソートとqsortのベンチマーク
http://codepad.org/K0qjjLqI
なんだけど、codepadのclockの扱いがちょっとおかしいらしく、たぶん機能してない。
僕の手元の環境では、stdlibのqsortのほうが早く、4〜5倍近い差があった。
--- set Data(n=500000) ---
mergesort: 406clock,
qsort: 110clock,
qsortとそっくり置き換えられるイメージで作ったけど、遅すぎてちょっと・・・という感じ。
再帰をなくせばもう少し早くなるんだろうけど、考えるのが疲れたのでまた今度。
比較関数には、比較演算子で大きいか小さいかを返すよりも、
比べる値同士を減算した結果を返すほうが速度的に良いらしい。
