最初に謝っておきます。本当なら数種類のソートを組んでいろいろなデータを使って実験すべきです。でも僕の力量ではそこまでできませんでした。
mixiの僕の日記を読んだ人なら分かると思うけど、僕は飲み屋で酔っ払いに絡まれやすい。
今を去ること1ヶ月ほど前。新宿で飲んでいたら酔っ払いに絡まれた。奇しくもわんくま勉強会の3次会でのこと。
その酔っ払いさんを仮にRさん。僕をCとするとその会話はこんな感じ。
R:「あのさぁ、あんどちんソートはどうやって選ぶんだ？」
C:「（何故僕指名？）データとか環境で決まるんじゃない？データの量が少なければバブルソートでいいし」
R:「そうじゃなくて、データの来る順番も量も不定の場合、それこそ何百万とかくるかもしれない場合」
C:「うぅん。クイックソートかヒープソートじゃないかなぁ」
R:「それだと組み込みの場合スタックを消費するだろ？」
C:「組み込みでそんな膨大なデータを扱う場合って、僕は経験ないし。組み込みでそんなデータを扱う場合は外部記憶装置に最適化された形でデータが保存されている場合がほとんどだと思うけど。カーナビの住所録とかなんて多分そうじゃないのかな？」
R:「動的に最適なソートを選択するアルゴリズムは無いのか？」
C:「分からないけど、アルゴリズムを選択するためにはデータを舐めなきゃならないだろうから、それ位なら妥当なアルゴリズムでソートするんじゃないかな？それからそういうのは組み込み屋よりDB屋の方が良く知ってるんじゃない？」
R:「DBはエンジン任せだろ？」
C:「だから、DBのエンジン作ってる人。」
R:「組み込みは速度に厳しいから（お前に）聞いてるんだ！」
C:「そう言われても…」
掻い摘んで書くとこんな感じで絡まれたわけですが（すいません。脚色してます）。
言われたような多量のデータまでを想定すると、クイックソートやヒープソートが良いかなぁと思いつつもデータの並びによっては指摘されたとおりスタックの消費量が心配ですね。再帰を使わない方法もありますが。
想定されるデータの形も量も不明確でソートを最適化となると確かに動的に最適なアルゴリズムを選択する必要はありそうです。
1つのデータのサイズが大きい場合は参照テーブル作ってテーブルだけバブルソートでソ ートした方がデータそのものを移動するクイックソートより早い場合もあるでしょう（さいきんエピさんとこでそんな話題があったような）。
更にデータの入り方ってのも影響するわけで、1件1件入ってくるようなものの場合（携帯の住所録とか。最初はまとめて入れるだろうけどその後は新規のデータを1件づつ入れる場合が多いでしょう）2分木で管理したほうが良い場合もあるし。
本来であれば色々書いてみて結果発表すべきですが、今月の勉強会の前には載せたかった話題なので、不完全ですが今日書いておきます。
出来れば色々やって考察を書きたいところですが、1ヶ月ほど考えても結局僕には最適解が答えられないので誰か答えてくれると嬉しいなぁ。