sortの比較

挿入ソートは, ほとんどソート済みのデータ列のソートが高速にできる
性質があるのだが, それがどれくらいなのかを簡単に調べてみた.

比較は, STLの std::sort(クイックソート)と
std::stable_sort(マージソート)と
std::__insertion_sort(挿入ソート).

100000のデータ列を20回ランダムにスワップしたものをソートすると
いうのを100回繰り返した.

結果からいうと, std::sortの圧勝.
たしかにスワップ回数が10以下なら挿入ソートに分があるが,
O(N^2)のアルゴリズムなので, スワップ回数が増えると急激に
計算時間がかかる.
マージソートはO(N log N)のアルゴリズムなので傾向はクイックソート
と同じだが, 計算時間は倍くらい遅かった.

データ列がほとんどソート済みという確信でもない限り,
素直にstd::sortを使うのが無難そうだ.