ソートについて（その２）

普通はライブラリ提供のソートを利用する。
それ以外なら、クイックソート。
ワーストケースが怖いなら、マージソート。
メモリーにきつい制限があるなら、コムソート。
さらに安定ソートを希望なら、In-place マージソート。

Quick Sort

なんでも良いから、たいてい早いやつ。
そんなアナタにおススメ。

クイックソート - Wikipedia
メモリーを潤沢に使えるなら、安定にすることも可能。

ピボット値の取り方が重要で、これが最小または最大あたりをとり続けると、ワーストケースになる。
とりあえず真ん中あたりを使えば、なんとかなる。
心配なら、先頭・中あたり・末尾の3値の中値を使えば、ほとんど大丈夫。
それでも心配な人は、別なソートをどうぞ。（それ以上の工夫はコストが高いか、別ソート）
ワーストケースを引く確率は相当低いと思うけど、引いた場合はIn-place Merge Sortより遅い。
悪意のある配列ソートを考慮するなら、使えない。

Comb Sort

とにかくメモリー使用量の少ないのをくれ、安定？どうでもいい。
そんなアナタにおススメ。

コムソート - Wikipedia
これも安定ソートではない。
売りはメモリー使用量とコードが単純なこと。
速度はマージソートに負けるかな。
ほとんどバブルソートなのに、ぐっと早くなるのは驚き。
ソート対象の比較回数は多め。

Merge Sort

メモリーはまあ使ってよいよ。クイック嫌い。
そんなアナタにおススメ。

マージソート - Wikipedia
安定ソートであるのも評価できる。
非再帰で工夫すれば、メモリー使用量はn/2．
ソート対象の比較回数が少ないのもメリットかな（比較コストが高い場合に有利）

個人的に一番好きなソート。
覚えるべき。

In-place Merge Sort

とにかくメモリー使用量の少ないのをくれ、あ、あと安定ね。
そんな贅沢なアナタにおススメ。

ksksts's blog: C#でin place merge sortを書いてみたらかなり遅かった
遅いよね。
スワップに工夫する余地がある気がするけど、、、。
そうでもないのかな。

既に整列済みのケースだけは、ただのマージソートより早い。
、、、けど、整列済み最速は、挿入ソート。