>>127
std::sortに渡すコンパレータは辻褄のあった結果を返さないといけないと仕様で決められている。
そうでない場合の動作は未定義。
つまり、でたらめな結果を返す可能性のあるコンパレータはstd::sortには使えない。

ソート関数を自作するか、コンパレータを検証する関数を追加するしかないだろうね。
いずれにしても矛盾を検知しようと思ったら、O(n log n)では済まないと思う。