僕が3大ソートって勝手に呼んでるのが マージ クイック ヒープ だ。 どれも「分けて」から「組み立てる」というやりかたでO(n log n)を実現してるのだけど、どの時点で「比較と並べ替え」をしているかで見ると面白い。 マージソートは「分ける」ときはそのままで「組み立てのときに比較と並び替え」をしている。 クイックソートは「分けながら比較と並び替え」をしていて「組み立てる」ときにはそのままにしている。 でヒープソートは「分けるときと組み立てるときの両方」で「比較と並び替え」をしている。

ネタ枠としてはボゴソートとスリープソートあたりを覚えておけばいいかな。

ソートは「ひとつだけ覚えておく」ならマージソートがいい。クイックソートみたいな落とし穴もない優等生。