【Java】ソート時のComparison method violates its general contractの原因

先日、Javaのプログラムでソートを実行した際に、以下のような例外に遭遇しました。

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
        at java.base/java.util.ComparableTimSort.mergeLo(ComparableTimSort.java:748)
        at java.base/java.util.ComparableTimSort.mergeAt(ComparableTimSort.java:485)
        at java.base/java.util.ComparableTimSort.mergeCollapse(ComparableTimSort.java:413)
        at java.base/java.util.ComparableTimSort.sort(ComparableTimSort.java:213)
        at java.base/java.util.Arrays.sort(Arrays.java:1249)
        at SortSample.main(SortSample.java:16)

実行したプログラムは以下のような感じです。

class SortSample {
  public static void main(String[] args) {
    int N = 500;
    ComparableObject[] a = new ComparableObject[N];
    // 中略(値を設定する処理)
    Arrays.sort(a);
  }
}

class ComparableObject implements Comparable<ComparableObject> {
  double d = 0;
  ComparableObject(double d) {
    this.d = d;
  }
  @Override
  public int compareTo(ComparableObject o) {
    if ( d != o.d ) {
      return d < o.d ? -1 : 1;
    } else {
      return 0;
    }
  }
}

ComparableObjectというクラスを、dの値の大小で比較可能なクラスとして定義し、それをソートしているだけに見えます。

Comparison method violates its general contract!というエラーメッセージを検索してみると、

• compare(A, B) < 0
• compare(B, A) < 0

が同時に成立してしまうようなケース、という情報が出てきました。(参考：Error: Comparison method violates its general contract! の対処法)
ただし、このサイトではcompareTo()の実装に問題があり、状況によってcompare(A, B) < 0とcompare(B, A) < 0の両方を満たしてしまうケースがある、というものでした。

今回のケースは、単純にdoubleの大小で比較しているだけなので、一見問題なさそうに見えます。

しかし、この単純な実装でもcompare(A, B) < 0とcompare(B, A) < 0を両方満たしてしまうケースがあることがわかりました。(本当は両方とも< 0が成り立つのではなく、両方とも> 0が成り立ちます)

それは、doubleの値がNaNの場合です。

試してみましょう。

double a = 0.0 / 0.0; // NaN
double b = 1.0;
System.out.println(String.format("a <  b  => %s", a < b));
System.out.println(String.format("a >  b  => %s", a > b));
System.out.println(String.format("a == b  => %s", a == b));
System.out.println(String.format("a != b  => %s", a != b));

実行結果：

a <  b  => false
a >  b  => false
a == b  => false
a != b  => true

恐ろしいことに、NaNとの比較をすると、<も>も==も成り立たず、!=のみが成り立つという状況になります。
さらに恐ろしいことに、aとbの両方ともNaNの場合も全く同じ結果になります。

なかなか気づきにくい原因なので、記事として残しておくことにしました。