トポロジカルソートのいんちき版
昔ICPCの合宿かなんかで、「全順序になってない順序に標準ライブラリのsort関数を適用する荒技トポロジカルソート」という話を聞いたことがあるような気がするんだけど、で、これもクイックソートなら大丈夫そうかなーと朧気に思った覚えがあるんだけど、一方でこれが上手く行かないように挿入ソートを組むのは簡単な気がする。これが可能なsortの実装というのはどういうものに限られるのだろうか。
半順序関係（特に推移律）を満たすならば選択法は安全に適用できる．それ以外は普通に適用してはまずいはず．
ところで stl::sort() はイントロソート（クイックソートとヒープソートのハイブリッド）と挿入法のハイブリッドだという話を聞いた覚えがあるから，いろいろまずいような．
〔追記１〕 クイックソートは注意深く実装すれば大丈夫ということに気づいた．それから，最悪計算量が O(n2) を下回るものはどの方法もだめという気がしてきた．クイックソートは最悪計算量が O(n2) であることに注意されたい．
〔追記２〕 半順序関係の比較演算だけを利用したソート（トポロジカルソート）の最悪計算量は O(n2) を下回ることがないとわかった．そのうち説明を書きます． 勘違いをしていたことが発覚したのでいったん撤回
