ソートって奥が深い

1. ワーストケースを考慮しなくていいような場所ではクイックソート、
2. 計算量を安定させたいときはヒープソート、マージソート、
3. プロトタイプでさっと組みたいときはバブルソート、
4. 挿入ソートって、O(n²)だしデータ構造もめんどくさいし(Cの場合ね)誰が使うの？

ぐらいにしか思ってなかったんですが。(←かなり近視眼的)

Wikipediaのソートに一覧がありますが、それぞれのソートの特徴がまとまってます。
そんなのを見ていくと、たとえば

• 並列処理しやすいか？
• 入ってくるデータがほぼソート済みデータだったりしないか？
• メモリの余裕は？
• 標準入力みたいなストリームだったら？

みたいな条件を加えると、選択すべきアルゴリズムも変わってきますね。
標準入力からのデータをソートするなら、入ってきたデータを逐次処理できる挿入ソートの方がメリットが出たりします。

Wikipediaのソートの項から辿っていくと、本当に勉強になります。